C++로 숫자를 1까지 줄이는 최소 연산 횟수 구하기

정수 하나가 입력으로 주어졌을 때, 이 숫자를 1로 만들기 위해 필요한 최소 연산 횟수를 구하는 것이 이 글의 목표입니다. 사용할 수 있는 연산은 다음 두 가지입니다.

숫자가 짝수라면 2로 나눕니다.
숫자가 홀수라면 1을 더하거나 뺍니다.

예시

입력 − Number = 28

출력 − 28을 1로 줄이는 최소 단계 수: 6

풀이 과정 −

28은 짝수 → 2로 나누기 = 14
14는 짝수 → 2로 나누기 = 7
7은 홀수 → 1 더하기 = 8
8은 짝수 → 2로 나누기 = 4
4는 짝수 → 2로 나누기 = 2
2는 짝수 → 2로 나누기 = 1

입력 − Number = 9

출력 − 9를 1로 줄이는 최소 단계 수: 4

풀이 과정 −

9는 홀수 → 1 빼기 = 8
8은 짝수 → 2로 나누기 = 4
4는 짝수 → 2로 나누기 = 2
2는 짝수 → 2로 나누기 = 1

알고리즘 접근 방식

이 문제는 재귀(Recursion)를 이용해 해결할 수 있습니다. 숫자가 짝수라면 단순히 2로 나누고, 홀수라면 (num − 1)과 (num + 1) 각각에 대해 재귀 호출을 수행한 뒤 더 작은 값을 선택하는 방식입니다.

정수형 입력값 Number를 받습니다.
함수 minWays(int num)는 num을 입력받아 1로 만드는 데 필요한 최소 연산 횟수를 반환합니다.
num이 1이면 더 이상 연산이 필요 없으므로 0을 반환합니다.
num % 2 == 0이라면 짝수이므로 num을 2로 나눈 값에 대해 재귀 호출합니다.
num이 홀수라면 tmp1 = minWays(num − 1)과 tmp2 = minWays(num + 1)을 구합니다.
tmp1과 tmp2 중 작은 값을 min에 저장하고, 1 + min을 반환합니다.
main 함수에서 결과를 출력합니다.

예제 코드

#include <iostream>
using namespace std;

int minWays(int num){
    int tmp1, tmp2, min;
    if (num == 1){
        return 0;                      // 1이 되면 연산 종료
    }
    else if (num % 2 == 0){            // 짝수인 경우
        tmp1 = minWays(num / 2);
        return (1 + tmp1);
    }
    else{                              // 홀수인 경우
        int tmp1 = minWays(num - 1);   // 1 빼기
        int tmp2 = minWays(num + 1);   // 1 더하기
        int min = tmp1 < tmp2 ? tmp1 : tmp2;
        return (1 + min);
    }
}

int main(){
    int Number = 21;
    cout << "Minimum steps to reduce " << Number << " to 1: " << minWays(Number);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Minimum steps to reduce 21 to 1: 6

성능 개선 팁

위의 순수 재귀 방식은 같은 값을 반복 계산할 수 있어 비효율적일 수 있습니다. 메모이제이션(Memoization)을 적용해 이미 계산한 결과를 저장하거나, 홀수일 때 num % 4가 3이면 1을 더하고 그렇지 않으면 1을 빼는 규칙을 활용하면 그리디(Greedy) 방식으로 O(log n) 시간에 해결할 수도 있습니다.