[BOJ 1463] 1로 만들기 2

#include <bits/stdc++.h>
using namespace std;
int N, dp[1000001], A[1000001];

int main() {
    cin >> N;
    dp[1] = 0;
    A[1] = -1;
    for(int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + 1;
        A[i] = i - 1;
        if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
            dp[i] = min(dp[i] , dp[i / 2] + 1);
            A[i] = i / 2;
        }
        if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) {
            dp[i] = min(dp[i], dp[i / 3] + 1);
            A[i] = i / 3;
        }
    }
    cout << dp[N] << '\n';
    for(int i = N; i >= 1; i = A[i]) {
        cout << i << ' ';
    }
}

DP 역추적 기본 문제이다. 1로 만들기 문제랑 비슷하게 풀면 되는데, 1로 만드는 방법의 경로들을 출력해야 하므로 이 경로들을 저장하는 배열들이 하나 필요하다. 그래서 배열에 이전에 왔던 경로들을 저장하면 되는데, 이 때 dp 배열의 값을 비교해서 이전 dp 배열보다 더 적은 횟수면 경로를 저장해줘야한다.