[이코테 DP] 02. 1로 만들기

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 문제 n까지 연산의 최솟값 구하기
// -1,/2,/3,/5 연산 가능
 
#define MAX 30001
int n,minN;
vector<int> dp(MAX);
int main()
{    
    ios::sync_with_stdio(false); // 계산시간 단축 // 문제마다 오류 유무 다름
    cin.tie(NULL); cout.tie(NULL);// 입출력 시간 단축
    cin >> n;
    
    // dp -1,/2,/3,/5 4가지 연산중 최소값을 고려
    // dp점화식: ai=min(ai-1, ai/2,ai/3,ai/5)+1 
    dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        minN = dp[i - 1]; // -1을 한 것까지의 최소 연산 횟수
        if (i % 2 == 0) { minN = min(minN, dp[i / 2]); }
        if (i % 3 == 0) { minN = min(minN, dp[i / 3]); }
        if (i % 5 == 0) { minN = min(minN, dp[i / 5]); }
        dp[i] = minN + 1; // 4가지 경우중 쵯솟연산에서 연산을 한 것이 i까지 최소연산
    }
    cout << dp[n];
    return 0;
}