백준 12856 1로 만들기 2

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

12852번: 1로 만들기 2

 

 

 

EXPLANATION

 

백준 1463 1로 만들기 문제(풀이 보러가기) 에서 N을 1로 만드는 최소 연산 횟수뿐만 아니라 그 과정에서 연산해서 나오는 수들을 추적하문제.

 

그냥 최소 연산 횟수 구하는 각 연산 과정에서 배열에 연산되서 나오는 수들을 저장하고 출력하면 된다.

따라서, 백준 1463 1로 만들기 문제 풀이에서 배열에 각 연산 과정에서 나오는 수들을 배열에 저장하는 코드를 추가하면 된다.

 

다만, 백준 1463 1로 만들기 문제에서 각 연산 과정 횟수의 크기 비교를 min을 이용해서 하였으나 이번에는 단순히 연산 과정 횟수뿐만 아니라 그 과정에서 연산되어 나온 수도 그에 따라 영향을 받아 저장해야 하므로 횟수의 크기 비교를 위해 if문을 이용한다.

 

CODE

#include <iostream>
using namespace std;

int dp[1000001];
int after_caculate[1000001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N;
    cin >> N;
    
    dp[1] = 0;    //1이 1이 되는 연산 횟수는 0. 연산할 필요 없이 그 자체가 1이므로.
    after_caculate[1] = -1;    //이미 1에 도달했으므로 1을 연산할 필요 없으므로, 1을 연산해서 나오는 다음 값은 없다.

    for (int i = 2; i <= N; ++i) {
        dp[i] = dp[i - 1] + 1;
        after_caculate[i] = i - 1;

        if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
            dp[i] = dp[i / 2] + 1;
            after_caculate[i] = i / 2;
        }
        if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
            dp[i] = dp[i / 3] + 1;
            after_caculate[i] = i / 3;
        }
    }

    cout << dp[N] << "\n";

    while (N != -1) {    //1까지 추적했으면 while문 종료.
        cout << N << ' ';
        N = after_caculate[N];
    }
    cout << '\n';

    return 0;
}