1로 만들기

1. 소스 코드

백준 https://www.acmicpc.net/problem/1463 문제 정리.

이 문제를 처음 접하는 순간 아무 생각이 들지 않았다. 나는 왜 이리 멍청할까 정도만 생각이 들지

모든 문제를 해결하기 위해서 먼저 완전탐색부터 고민하면서 속도 개선을 위해서 하나 하나 개선해 가는 식으로 여기에 정리한다. 참고로 여러 사람들이 해 놓은 코드를 참조하였다.

아래 코드는 완전 탐색으로 구현한 내용이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include <iostream>   unsigned int min = 0xFFFFFFFF;   void f(int n, unsigned int d) {     if(n == 1)     {         if(min > d)         {             min = d;         }           return;     }       f(n-1, d+1);       if(n%2 == 0)     {         f(n/2, d+1);     }           if(n%3 == 0)     {         f(n/3, d+1);     } }   int main() {     int n;     std::cin >> n;       f(n, 0);       std::cout << min << std::endl;     return 0; }

2. DP 코드

dp[n] = f(n-1) + 1로 완전탐색 루틴에서 가장 왼쪽 노드의 값에서 차례되로 dp[n]값을 구하고 f(n/2) 또는 f(n/3)에서 그 값이 더 작으면 dp[n]을 update하는 식으로 처리하면서 최종값을 얻는다.

결론적으로 위 완전 탐색에서 f함수 두번째 매개변수 처리를 dp배열로 어떻게 처리하느냐가 관건으로 보인다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include <iostream>   int dp[10000000 + 1];   int f(int n) {     if(n == 1)     {         return 0;     }       dp[n] = f(n-1) + 1;       if(n%2 == 0)     {         int d = f(n/2) + 1;         if(dp[n] > d)         {             dp[n] = d;         }     }       if(n%3 == 0)     {         int d = f(n/3) + 1;         if(dp[n] > d)         {             dp[n] = d;         }     }       return dp[n]; }   int main() {     int n;     std::cin >> n;       std::cout << f(n) << std::endl;     return 0; }

결론적으로 재귀함수 호출을 모두 제거하면 아래와 같은 코드로 완성할 수 있다.

위의 재귀함수 호출 코드를 하나하나 따라가 보면 결국 재귀함수 호출 내에서 DP값이 모두 구해져 있어서

DP값으로 재귀함수 변환값은 대체된다. 이를 통해서 재귀호출 구문은 아래처럼 모두 없앨 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <iostream>   int dp[10000000 + 1];   int main() {     int n;     std::cin >> n;       dp[0] = 0;     dp[1] = 0;     dp[2] = 1;     dp[3] = 1;       for(int i = 4; i <= n; i++)     {         int d1 = 0x1FFFFFFF, d2 = 0x1FFFFFFF, d3 = 0x1FFFFFFF;           d1 = dp[i-1];                   if(i%2 == 0)         {             d2 = dp[i/2];         }           if(i%3 == 0)         {             d3 = dp[i/3];         }           dp[i] = std::min(std::min(d1, d2), d3) + 1;           //std::printf("%d %d %d %d %d \n", i, d1, d2, d3, dp[i]);     }       std::cout << dp[n] << std::endl;     return 0; }