C++로 N에서 M까지 도달하는 최소 연산 횟수 구하기

두 개의 정수 N과 M이 주어졌을 때, 아래의 두 가지 연산만을 사용하여 N에서 M까지 도달하는 데 필요한 최소 연산 횟수를 구하는 문제입니다.

• 숫자 x에 2를 곱합니다 → x는 2*x가 됩니다.
• 숫자 x에서 1을 뺍니다 → x는 x-1이 됩니다.

예를 들어 N = 4, M = 6이라면 정답은 2입니다. 먼저 N에서 1을 빼면 3이 되고, 그 값에 2를 곱하면 6이 되기 때문입니다. 즉, 두 번의 연산만으로 목표에 도달할 수 있습니다.

접근 방법: 문제를 거꾸로 생각하기

이 문제는 방향을 뒤집으면 훨씬 간단하게 해결할 수 있습니다. N에서 출발해 M으로 가는 대신, M에서 출발해 N으로 가는 과정으로 바꾸는 것입니다. 그러면 연산도 자연스럽게 반전되어 다음과 같이 바뀝니다.

• 숫자가 짝수라면 2로 나눕니다.
• 숫자에 1을 더합니다.

역방향 변환 후 최소 연산 횟수는 다음 규칙에 따라 계산할 수 있습니다.

• N > M인 경우: 두 수의 차이를 그대로 반환합니다. M에 1을 계속 더해 N과 같아질 때까지의 횟수가 곧 정답이기 때문입니다.
• N < M인 경우: M이 N보다 작아질 때까지 2로 나눕니다. 이때 M이 홀수라면 먼저 1을 더한 뒤 나눠야 합니다. M이 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

위 코드는 while 루프 안에서 M이 홀수일 경우 1을 더하고, 짝수일 때마다 2로 나누는 과정을 반복합니다. 루프가 종료된 후에는 남은 차이(n - m)를 더해 최종 연산 횟수를 반환합니다. 이 알고리즘의 시간 복잡도는 O(log M)으로 매우 효율적입니다.