DP_백준_1로 만들기_1463

1. dp[n] : 연산 3 개를 사용하여 n을 1을 만들때 연산 사용 횟수의 최솟값.

2. 점화식 : dp[n] = min(dp[n/3], dp[n/2], dp[n-1]) +1 

3. 초기화 : dp[0] = 0, dp[1] =0

시간 복잡도 : O(N)

N을 - - - 해서 변형을 해서 1로 만든다.

#include <iostream>
using namespace std;
 
int d[1000001];
int dp(int num) {
    int tmp;
    if (num <= 1) {
        return 0;
    } // Exception Handling
    if (d[num] > 0) {
        return d[num];
    } // Memoization
 
    d[num] = dp(num - 1) + 1;
    if (num % 2 == 0) {
        tmp = dp(num / 2) + 1;
        if (tmp < d[num]) {
            d[num] = tmp;
        }
    }
    if (num % 3 == 0) {
        tmp = dp(num / 3) + 1;
        if (tmp < d[num]) {
            d[num] = tmp;
        }
    }
    return d[num];
    // min(dp[n/3], dp[n/2], dp[n-1])
}
 
int main() {
    d[0] = 0;
    d[1] = 0;
    //Initialize
 
    int input;
    cin >> input;
    cout << dp(input) << endl;
    return 0;
}