두 개의 정수 N과 M이 있다고 가정합니다. 주어진 연산을 수행하여 N에서 M에 도달하는 최소 단계 수를 찾아야 합니다. -
- x에 2를 곱하면 x는 2*x가 됩니다.
- 숫자 x에서 1을 빼면 x – 1이 됩니다.
N =4이고 M =6이면 출력은 2가 됩니다. 따라서 N에 대해 2번 작업을 수행하면 N이 3이 되고 업데이트된 N 값에 대해 1번 작업을 수행하므로 2 * 3 =6이 됩니다. 따라서 최소 단계 수는 2입니다.
이 문제를 해결하기 위해 우리는 다음 규칙을 따를 것입니다 -
- M에서 시작하는 숫자 N을 취하는 것처럼 문제를 되돌릴 수 있으므로 새로운 두 연산은 다음과 같습니다.
-
- 짝수일 때 2로 나누기
- 숫자에 1 더하기
- 이제 최소 작업 수는
- N> M이면 그 차이를 반환하므로 N이 될 때까지 단계 수는 M에 1을 더합니다.
- 그렇지 않으면 N
예시
#include<iostream>
using namespace std;
int countMinimumSteps(int n, int m) {
int count = 0;
while(m > n) {
if(m % 2 == 1) {
m++;
count++;
}
m /= 2;
count++;
}
return count + n - m;
}
int main() {
int n = 4, m = 6;
cout << "Minimum number of operations required: " << countMinimumSteps(n, m);
} 출력
Minimum number of operations required: 2