C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1463번:1로 만들기 답

DP문제입니다.

더 작은 문제 또한 기존의 문제와 푸는 법이 같기 때문에 점화식을 세워서 풉니다.

#include <iostream>
#include <algorithm>
using namespace std;
int D[1000001];
 
int main(void) {
 
    int N;
    cin >> N;
    for (int i = 2; i <= N; i++)
    {
        D[i] = D[i - 1] + 1;
        if (i % 2 == 0)
            D[i] = min(D[i], D[i / 2] + 1);
        if (i % 3 == 0)
            D[i] = min(D[i], D[i / 3] + 1);
    }
    cout << D[N] << '\n';
}