[DP (동적 프로그래밍) / BOJ 12852 / C++] 1로 만들기 2

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

12852번: 1로 만들기 2

이번 문제는 그냥 dp하나만 보면 간단하게 풀릴 수 있었는데 .. 

최소값을 구하는 것 뿐만 아니라 최솟값이 나오기까지의 과정도 보여줘야한다.

 

즉, dp 진행 중, 중간의 값들을 계속해서 "Tracing" 해야한다.

 

다행스럽게도, 잘 생각해보면 특정값 X는 최소의 연산횟수를 보장하는 경로가 단 한가지 연산 밖에 없다.

(여러 경로가 있지만, 그럼에도 최선의 선택은 1개뿐.)

 

예를 들어, 10의 경우는 9, 9의 경우는 3, 3의 경우는 1이 전부다.

10 9 3 1

즉 이것을 새로운 DP의 값으로 보여줄 수 있다.

이를 활용해 dp값이 갱신될때마다 dp2를 갱신시켜 값을 계속 트레이싱한다.

#include <bits/stdc++.h>

using namespace std;


int dp[1000001], dp2[1000001], N;

int go(int cal){
    if(cal<1) return INT_MAX;
    if(cal==1) return 0;
    
    int &mid = dp[cal];
    if(mid!=INT_MAX) return mid;
    
    if(cal%3==0){
        int m1 = go(cal/3)+1;
        if(mid > m1){
            dp2[cal]=cal/3;
            mid = m1;
        }
    }
    
    if(cal%2==0){
        int m2 = go(cal/2)+1;
        if(mid > m2){
            dp2[cal]=cal/2;
            mid = m2;
        }
    }
    
    int m3 = go(cal-1)+1;
    if(mid > m3){
        dp2[cal]=cal-1;
        mid = m3;
    }
    
    
    return mid;
    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    fill(&dp[0], &dp[0]+1000001, INT_MAX);
    
    cin >> N;
    
    
    int answer = go(N);
    
    cout << answer << '\n';
    
    cout << N << ' ';
    for(int i = N; i > 1; i=dp2[i]){
        cout << dp2[i] << ' ';
    }
    
    cout << '\n';
}