[1463번] 1로 만들기 - 동적계획법 [C++]

이 문제는 동적계획법을 이용한 기본적인 문제로 처음 동적계획법을 접한다면 쉽지 않을 수 있다.

동적계획법이란 문제를 서브 문제로 나누어서 그것을 결합하여 결론에 도달하는 방법이다.

연산횟수를 줄이는 데 목표를 가지고 있다.

이 문제는 Bottom-up방법(동적계획법)을 이용하였다.

다른 방법도 무수히 존재하는 문제이다.

예외를 찾기가 힘든데 만약 어려움을 겪고 있다면

1793을 넣어보자.ㅎㅎ

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