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

문제

https://www.acmicpc.net/problem/1463

 

풀이

이 문제는 다이나믹 프로그래밍 문제이다.

 

dp[i] = min(dp[i+1] + 1, dp[i]) (모든 i에 대해)
dp[i] = min(dp[2i] + 1, dp[i]) (i가 2의 배수일 때)
dp[i] = min(dp[3i] + 1, dp[i]) (i가 3의 배수일 때)

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int dp[1000001] = { 0, };
int main() {
    int n;

    cin >> n;

    for (int i = n; i >= 1; i--) {
        if (dp[i - 1] == 0) {
            dp[i - 1] = dp[i] + 1;
        }
        else {
            dp[i - 1] = min(dp[i - 1], dp[i] + 1);
        }

        if (i % 2 == 0) {
            if (dp[i / 2] != 0) {
                dp[i / 2] = min(dp[i / 2], dp[i] + 1);
            }
            else
            {
                dp[i / 2] = dp[i] + 1;
            }
        }

        if (i % 3 == 0) {
            if (dp[i / 3] != 0) {
                dp[i / 3] = min(dp[i / 3], dp[i] + 1);
            }
            else
            {
                dp[i / 3] = dp[i] + 1;
            }
        }
    }

    cout << dp[1];

    return 0;
}