[C++] 백준 1463번 1로 만들기

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