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

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

12852번: 1로 만들기 2

풀이

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

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

그리고 연산의 순서대로 출력을 해야 하므로 1로 가는 경로에 있는 다음 값을 배열에 저장하였다.

ex) arr[16] = 8, arr[8] = 4, arr[4] = 3, arr[3] = 1

#include <iostream>

using namespace std;

int arr[1000005];
int history[1000005];
int n;

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

    cin >> n;
    for(int i = 2; i <= n; i++){
        arr[i] = arr[i-1] + 1;
        history[i] = i-1;
        if(i%2 == 0 and arr[i] > arr[i/2] + 1){
            arr[i] = arr[i/2] + 1;
            history[i] = i/2;
        }
        if(i%3 == 0 and arr[i] > arr[i/3] + 1){
            arr[i] = arr[i/3] + 1;
            history[i] = i/3;
        }
    }
    cout << arr[n] << "\n";
    int x = n;
    cout << n << " ";
    while(history[x] != 0){
        cout << history[x] << " ";
        x = history[x];
    }
}