C++로 n을 0으로 줄이는 최소 연산 횟수 구하는 프로그램

숫자 n이 하나 주어집니다. 우리는 다음 세 가지 연산 중 하나를 자유롭게 선택해 수행할 수 있습니다.

n에서 1을 뺀다.
n이 짝수라면 n / 2만큼 뺀다.
n이 3으로 나누어 떨어지면 2 * (n / 3)만큼 뺀다.

최종 목표는 위 연산들을 반복 적용하여 n을 0으로 만들 때 필요한 최소 연산 횟수를 구하는 것입니다.

예를 들어 입력이 n = 16이라면 출력은 5가 됩니다. 16은 짝수이므로 n/2씩 네 번 감소시켜 1을 만들고, 마지막으로 1을 빼서 0이 되기 때문입니다. 따라서 총 5번의 연산이 필요합니다.

접근 방법

이 문제는 단순히 큰 폭의 연산만 골라 수행하는 그리디(greedy) 방식으로는 항상 최적해를 보장할 수 없습니다. 따라서 가능한 모든 경로를 탐색하되, 이미 계산한 값을 재활용하는 메모이제이션(memoization) 기반 DFS(깊이 우선 탐색)로 해결하는 것이 효율적입니다.

알고리즘은 다음 단계로 진행됩니다.

계산 결과를 캐싱할 맵 dp를 하나 정의한다.
x를 인자로 받는 함수 dfs()를 정의한다.
ret := x 로 초기화한다.
x가 dp에 이미 존재하면 dp[x]를 그대로 반환한다.
x <= 0이면 x를 반환한다.
x == 1이면 1을 반환한다.
md2 := x mod 2, md3 := x mod 3 을 계산한다.
ret := { ret, md2 + 1 + dfs((x - md2) / 2), md3 + 1 + dfs((x - md3) / 3) } 중 최솟값으로 갱신한다.
dp[x] = ret 을 저장한 뒤 ret을 반환한다.
main 함수에서 dfs(n)을 호출하고 그 결과를 반환한다.

여기서 md2 + 1 + dfs(...) 항은 "x를 2로 나누어 떨어지도록 만들기 위해 md2번 1을 빼고, 한 번의 연산으로 절반으로 줄인 뒤, 남은 값에 대해 다시 탐색한다"는 의미입니다. 3으로 나누는 경우(md3 관련 항)도 같은 원리로 동작합니다. 두 분기를 모두 고려하면서 최솟값을 선택하기 때문에 항상 최적의 답을 얻을 수 있으며, 메모이제이션 덕분에 각 상태는 한 번만 계산되어 실행 속도가 매우 빠릅니다.

예시 구현

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
unordered_map <int, int> dp;
int dfs(int x){
   int ret = x;
   if(dp.count(x))
      return dp[x];
   if(x <= 0)
      return x;
   if(x == 1)
      return 1;
   int md2 = x % 2;
   int md3 = x % 3;
   ret = min({ret, md2 + 1 + dfs((x - md2) / 2), md3 + 1 + dfs((x - md3) / 3)});
   return dp[x] = ret;
}
int solve(int n) {
   return dfs(n);
}
int main(){
   int n = 16;
   cout << solve(n);
}