[이코테/DP/C++] 1로 만들기

#include <bits/stdc++.h>

using namespace std;
int n;
int d[30001]; //DP 테이블 초기화

int main() {
    cin >> n;
    d[0] = 0;
    d[1] = 1;

    //다이나믹 프로그래밍 진행(보텀업)
    for(int i=2; i<n; i++){
        //1을 빼는 경우
        d[i] = d[i-1] + 1;
        //2로 나누어 떨어지는 경우
        if(i % 2 == 0) d[i] = min(d[i], d[i/2]+1);
        //3으로 나누어 떨어지는 경우
        if(i % 3 == 0) d[i] = min(d[i], d[i/3]+1);
        //5로 나누어 떨어지는 경우
        if(i % 5 == 0) d[i] = min(d[i], d[i/5]+1);
    }

    cout<<d[n]<<endl;

    return 0;
}