1로 만들기

1. 소스 코드

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

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

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

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

#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배열로 어떻게 처리하느냐가 관건으로 보인다.

#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값으로 재귀함수 변환값은 대체된다. 이를 통해서 재귀호출 구문은 아래처럼 모두 없앨 수 있다.

#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; }