C++로 해결하는 정수 대체(Integer Replacement) 문제

문제 소개

양의 정수 n이 주어졌을 때, 다음 두 가지 연산을 수행할 수 있다고 가정해 보겠습니다.

n이 짝수라면, n을 n/2로 대체합니다.
n이 홀수라면, n을 n+1 또는 n-1 중 하나로 대체합니다.

우리가 구해야 할 것은 n을 1로 만들기 위해 필요한 최소 대체 횟수입니다.

예를 들어 n이 7이라면 정답은 4입니다. 7 → 8 → 4 → 2 → 1 또는 7 → 6 → 3 → 2 → 1의 경로를 거치면 딱 4번의 연산만으로 1에 도달할 수 있기 때문입니다.

문제 해결 접근법

이 문제는 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.

연산 횟수를 저장할 ret을 0으로 초기화하고, n에 입력값 x를 대입합니다.
n이 1보다 큰 동안 아래 과정을 반복합니다.
- n이 짝수라면 n을 2로 나눕니다(n = n / 2).
- n이 홀수라면 다음 규칙을 적용합니다.
  - n이 3이거나, n을 2로 나눈 몫이 짝수라면 n에서 1을 뺍니다.
  - 그 외의 경우에는 n에 1을 더합니다.
반복 한 번당 ret을 1씩 증가시킵니다.
루프가 종료되면 ret을 반환합니다.

왜 이런 선택이 최적일까요?

홀수일 때 +1과 -1 중 무엇을 고르느냐가 관건입니다. 이진수 관점에서 보면 그 이유가 명확해집니다.

n이 3인 경우: 3 → 2 → 1이 최단 경로이므로 반드시 1을 빼야 합니다.
n의 이진 표현이 …01로 끝나는 경우(n/2가 짝수): 1을 빼면 곧바로 2로 나눌 수 있어 유리합니다.
n의 이진 표현이 …11로 끝나는 경우: 1을 더하면 자리올림으로 연속된 비트가 사라져 이후 나눗셈 횟수를 크게 줄일 수 있습니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    int integerReplacement(int x) {
        int ret = 0;
        lli n = x;
        while(n > 1){
            if(n % 2 == 0){
                n >>= 1;
            }
            else if(n & 1){
                if(n == 3 || (((n >> 1) & 1 )== 0)){
                    n--;
                } else {
                    n++;
                }
            }
            ret++;
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.integerReplacement(7));
}

여기서 n을 long long int(lli)로 선언한 점에 주목할 필요가 있습니다. 입력이 int의 최댓값(2,147,483,647)처럼 큰 홀수일 경우 n+1 연산 과정에서 오버플로가 발생할 수 있기 때문입니다.

실행 결과

입력:

출력:

복잡도 분석