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

#include <iostream>
using namespace std;
int d[1000001],ans[1000001];
int go(int n) {
    int out;
    int m = 2000000000;
    int tmp;
    if (n == 1) {
        return 0;
    }
    if (d[n] > 0) {
        return d[n];
    }
    tmp = go(n - 1) + 1;
    if (m > tmp)
    {
        out = n - 1;
        m = tmp;
    }
    if (n % 2 == 0) {
        tmp = go(n / 2) + 1;
        if (m > tmp) {
            m = tmp;
            out = n / 2;
        }
    }
    if (n % 3 == 0) {
        tmp = go(n / 3) + 1;
        if (m > tmp) {
            m = tmp;
            out = n / 3;
        }
    }
    ans[n] = out;
    return d[n] = m;
}
int main() {
    int n;
    cin >> n;
    cout << go(n) << '\n';
    cout << n << ' ';
    while (ans[n] != 1)
    {
        cout << ans[n] << ' ';
        n = ans[n];
    }
    cout << '1' << '\n';
}