[PS] 백준 1463번 - 1로 만들기

DP를 사용하여 가능한 최수 경우의 수를 Bottom-Up 방식으로 구해준다.

#include <iostream>

using namespace std;

int main() {
    int N, DP[1000001];
    cin >> N;
    DP[1]=0;
    for(int i=2; i<=N; i++) {
        DP[i]=DP[i-1]+1;
        if(!(i%3)) DP[i]=min(DP[i], DP[i/3]+1);
        if(!(i%2)) DP[i]=min(DP[i], DP[i/2]+1);
    }
    cout << DP[N];
}