https://www.acmicpc.net/problem/1463
점화식을 사용하는 문제는 아니지만, 매번 새로 계산을 하는 것이 아니라 이미 계산된 값은 배열에 저장해서 시간을 줄여야 하는 문제였다.
먼저 배열에 n의 범위보다 큰 값을 저장해두고,
2부터 n까지 모든 단계에서, 세 가지 연산 중 1로 만들기에 가장 적은 횟수를 필요로 하는 것을 선택한다.
#include <iostream>
using namespace std;
const int MAX = 1e7;
int dp[1000001];
int main()
{
int n;
cin >> n;
dp[1] = 0;
for(int i=2; i<=n; i++){
dp[i] = MAX;
}
for(int i=2; i<=n; i++){
dp[i] = dp[i-1] + 1;
if(i % 3 == 0) dp[i] = min(dp[i], dp[i/3] + 1);
if(i % 2 == 0) dp[i] = min(dp[i], dp[i/2] + 1);
}
cout << dp[n];
return 0;
}