문제 이해하기
양의 정수 x가 주어졌을 때, 다음과 같은 형태의 수식을 작성한다고 가정해 보겠습니다.
x (op1) x (op2) x (op3) x ...
여기서 op1, op2 등은 각각 덧셈(+), 뺄셈(-), 곱셈(*), 나눗셈(/) 중 하나입니다. 예를 들어 x = 3이라면 3 * 3 / 3 + 3 - 3처럼 수식을 작성할 수 있으며, 이 수식의 계산 결과는 3이 됩니다.
적용되는 규칙
- 나눗셈 연산자(/)는 유리수를 결과로 반환합니다.
- 괄호는 어떤 위치에도 사용할 수 없습니다.
- 일반적인 연산자 우선순위를 따릅니다. 즉, 곱셈과 나눗셈이 덧셈과 뺄셈보다 먼저 계산됩니다.
- 단항 음수(unary negation) 연산자는 사용할 수 없습니다.
우리의 목표는 주어진 target 값과 동일한 결과를 만드는 수식을 작성하되, 사용하는 연산자의 개수를 최소화하는 것입니다. 즉, 필요한 최소 연산자 개수를 구해야 합니다.
예제
입력이 x = 4, target = 15라고 가정해 봅시다. 이때 출력은 3입니다. 그 이유는 15를 4 * 4 - 4 / 4로 표현할 수 있기 때문입니다. 이 수식은 16 - 1 = 15이며, 곱셈, 뺄셈, 나눗셈 총 세 개의 연산자만 사용합니다.
풀이 접근 방법
이 문제는 재귀적으로 해결할 수 있습니다. 핵심 아이디어는 x의 거듭제곱 값을 활용해 target에 가장 가까운 지점을 찾은 뒤, 남은 차이를 다시 같은 방식으로 표현하는 것입니다. 알고리즘은 다음과 같습니다.
- target이 x와 같다면 0을 반환합니다.
- x가 target보다 크다면 min((x - target) * 2, (target * 2) - 1)을 반환합니다. 이는 x를 직접 빼는 경우와 1을 반복해서 더하고 빼는 경우를 비교하는 것입니다.
- sum을 x로 초기화하고 t를 0으로 설정한 뒤, sum이 target 이상이 될 때까지 sum에 x를 곱하면서 t를 1씩 증가시킵니다.
- sum이 target과 정확히 같다면 t를 반환합니다.
- 그렇지 않다면 두 가지 경우를 재귀적으로 탐색합니다.
- r: sum - target < target인 경우, (sum - target)을 표현하는 데 필요한 연산자 수에 t를 더한 값
- l: (target - sum / x)를 표현하는 데 필요한 연산자 수에 t - 1을 더한 값
- 두 값 중 작은 값에 1을 더해 최종 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int leastOpsExpressTarget(int x, int target) {
if(target == x) return 0;
if(x > target){
return min((x - target) * 2, (target * 2) - 1);
}
lli sum = x;
int t = 0;
while(sum < target){
sum *= x;
t++;
}
if(sum == target) return t;
int l = INT_MAX;
int r = INT_MAX;
if(sum - target < target){
r = leastOpsExpressTarget(x, sum - target) + t;
}
l = leastOpsExpressTarget(x, target - (sum / x)) + t - 1;
return min(l, r) + 1;
}
};
main(){
Solution ob;
cout << (ob.leastOpsExpressTarget(4, 15));
}
입력
4, 15
출력
3
위 실행 결과에서 확인할 수 있듯이, x = 4와 target = 15가 주어졌을 때 프로그램은 3을 출력합니다. 이는 4 * 4 - 4 / 4라는 수식으로 15를 정확히 표현하면서 연산자를 세 개만 사용했음을 의미합니다.