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

12852번: 1로 만들기 2

dp를 이용한 문제이다. 먼저 배열 dp에 dp[1] = 0, 나머지는 큰 값으로 초기화 해주었다. N에서 1이 아니라 1에서 N 순서로 반복문을 돌면서 최솟값을 구해주었다. 각 조건에 맞을 경우의 최솟값을 구해주고 1을 더해주는 것을 반복하며 dp[N]에 결과가 저장되도록 해주었다. 지나온 순서를 출력할 때는 N에서 시작하여 1 차이가 나는 조건을 찾아 차례대로 출력해주었다. 처음에는 이 문제를 dfs로 접근을 했는데 시간 초과가 났었다. dp 문제를 많이 풀어봐야 겠다.

#include <iostream>

using namespace std;

int N;
int dp[1000001];

void solution() {
    dp[1] = 0;
    for (int i = 2; i <= N; i++) {
        dp[i] = 987654321;
    }

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

        dp[i]++;
    }

    cout << dp[N] << endl;

    while (1) {
        cout << N << " ";

        if (N <= 1) break;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    solution();

    return 0;
}