양의 정수 x가 있다고 가정하고 x (op1) x (op2) x (op3) x ... 형식의 표현식을 작성합니다. 여기서 op1, op2 등은 연산자입니다. 그리고 이러한 연산자는 더하기, 빼기, 곱하기 또는 나누기가 될 수 있습니다. 예를 들어 x =3일 때 3 * 3 / 3 + 3 - 3이라고 쓸 수 있습니다. 값은 3입니다. 몇 가지 규칙이 있으며 다음과 같습니다. -
-
나누기 연산자(/)는 유리수를 반환합니다.
-
어디에도 괄호가 없습니다.
-
우리는 일반적인 연산 순서를 사용합니다. 곱셈과 나눗셈은 덧셈과 뺄셈보다 우선 순위가 높습니다.
-
단항 부정 연산자는 허용되지 않습니다.
표현식이 주어진 대상과 같도록 가장 적은 수의 연산자로 표현식을 작성해야 합니다. 따라서 가장 적은 수의 연산자를 찾습니다.
따라서 입력이 x =4, target =15인 경우 15를 4*4-4/4로 표현할 수 있으므로 출력은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
대상이 x와 같으면 -
-
x> 대상이면 -
-
(x - target) * 2 및 (target * 2) - 1의 최소값을 반환합니다.
-
-
-
합계 :=x, t :=0
-
합계
-
합계 :=합계 * x
-
(t를 1씩 증가)
-
-
합계가 대상과 같으면 -
-
리턴 t
-
-
l :=정보, r :=정보
-
합계 - 대상 대상인 경우 -
-
r :=minimumOpsExpressTarget(x, 합계 - 대상)
-
-
l :=minimumOpsExpressTarget(x, 대상 - (합 / x))
-
1 + l과 r의 최소값을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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