(C++) 백준 1463번 - 1로 만들기

문제 링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

풀이

다이나믹 프로그래밍을 활용하여 풀이하였다.

입력이 1일 때 0, 입력 2일 때 1이라는 초기값을 부여해 주고 그 이후에 상황에 맞춰 1씩 더해주는 방식으로 풀이하였다.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int arr[1000002];
int X;

int main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);
    cout.tie(0);

    cin >> X;
    arr[2] = 1;
    for(int i = 3; i <= X; i++){
        arr[i] = arr[i-1] + 1;
        if(i%2 == 0) arr[i] = min(arr[i], arr[i/2]+1);
        if(i%3 == 0) arr[i] = min(arr[i], arr[i/3]+1);
    }
    cout << arr[X];
}