[Gold Ⅴ] 1로 만들기 2

[문제 위치]

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

[문제 풀이]

태그에 역추적이 있어 그걸로 문제를 풀어보았다.

X에서 내려오는 것이 아니라 다이나믹 프로그래밍 방식 중 바텀업을 통하여 아래에서 부터 X를 만드는 경우의 수를 찾아나갔다.

X를 1 빼거나 2로 나누거나 3으로 나누기 때문에 1큰수, 2를 곱한 수, 3을 곱한 수에 횟수를 1 더한 값을 더해 저장해주었다.

이후 두 번째 줄에는 지금까지의 경로를 출력하라 나와있는데 그 과정을 따지지 않으므로 다시 위에서부터 내려오면 된다.

아래는 이를 구현한 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> dp(N + 1, 0);

    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
        if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);
    }

    cout << dp[N] << endl;

    int cur = N;
    while (true) {
        cout << cur;
        if (cur == 1) break;
        cout << ' ';

        if (cur % 3 == 0 && dp[cur] == dp[cur / 3] + 1) cur /= 3;
        else if (cur % 2 == 0 && dp[cur] == dp[cur / 2] + 1) cur /= 2;
        else cur -= 1;
    }

    return 0;
}