[BOJ-12852]1로만들기2

1로만들기 문제에서

최소연산이 되는 수들의 순서인 것을 추가 출력하는 문제이다. 

순서는 입력으로 주어진 X 부터 1까지 출력한다. 

dp[수][2] 로 설정한다. 

dp[수][0] 자리에는 동일하게 연산의 횟수를 넣고

dp[수][1] 자리에는 이전 최소연산이 되는 수의 위치를 저장한다. 

벡터를 이용하여 1부터 시작하여 입력 수인 X 까지 경로를 확보한 후 

벡터 rbegin 메소드를 이용하여, rend 까지 거꾸로 출력해주면 이 문제의 답을 구할 수 있다. 

#include<cstdio>
#include<vector>
using namespace std;
/*
input : [1,1E+6]
output : [0,1E+6]
cond-1 : X%3 == 0 -> X%3
cond-2 : X%2 == 0 -> X%2
cond-3 : X--
*/
vector<int> seq;
const int INF = 1111111;
int dp[1111111][2];
void init_dp(){
    for(int i = 0 ; i < INF ; i++) dp[i][0] = INF;
}
int min_2(int a, int b){
    return (a>b)?b:a;
}
void dy(int x){
    if(x==0) return;
    if(x%3 == 0){
        if(dp[x/3][0] > dp[x][0]+1){
            dp[x/3][0] = dp[x][0]+1;
            dp[x/3][1] = x;
        }
    }
    if(x%2 == 0){
        if(dp[x/2][0] > dp[x][0]+1){
            dp[x/2][0] = dp[x][0]+1;
            dp[x/2][1] = x;
        }
    }
    if(dp[x-1][0] > dp[x][0]+1){
        dp[x-1][0] = dp[x][0]+1;
        dp[x-1][1] = x;
    }
}
 
int main(){
    int X; scanf("%d", &X);    
    
    // operation
    init_dp();
    dp[X][0] = 0;
    for(int i = X ; i > 0 ; i--){
        dy(i);
    }
    // end operation 
 
    printf("%d\n",dp[1][0]);
    int order = 1;
    while(1){
        seq.push_back(order);
        if(order == X) break;
        order = dp[order][1];
    }
    for(auto iter = seq.rbegin() ; iter != seq.rend(); iter++){
        printf("%d ",*iter);
    }
    return 0;
}