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

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

백준 DP 연습 문제다.

DP는 크게 상향식, 하향식으로 나뉠 수 있는데, 이 문제는 상향식으로 풀었다.

 

즉, 초기값을 낮은곳에 잡고 이를 활용해 목적숫자로 커지며 답을 갱신하는 구조다.

작은 답이 큰 답의 도출에 이용되는 DP.

#include <iostream>
#include <algorithm>
 
#define maxlen 1000000+1
#define INF 987654321
using namespace std;
 
int N;
int arr[maxlen];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < maxlen; i++) arr[i] = INF;
    arr[1] = 0;
    for (int i = 1; i <= N; i++){
        if (i == N){
            cout << arr[N] << '\n';
            break;
        }
        if (i + 1 < maxlen){
            arr[i + 1] = min(arr[i] + 1, arr[i + 1]);
        }
        if (i * 2 < maxlen){
            arr[i * 2] = min(arr[i] + 1, arr[i * 2]);
        }
        if (i * 3 < maxlen){
            arr[i * 3] = min(arr[i] + 1, arr[i * 3]);
        }
    }
    return 0;
}