1로 만들기 2

12852번: 1로 만들기 2

문제는 두개로 나눌 수 있다.

1. 주어진 n을 1로 만드는 최소연산횟수를 구하는 것과

2. 최소연산횟수로 1을 만드는 과정에 있는 수(경로)를 구하는 것이다.

 

변수 설명

dp : n을 1로 만드는 최소연산횟수

pre: n을 1로 만드는 과정에서 n에서 1개의 연산을 하고 난 후의 수.

 

대충 짜보자면

1 ) dp[n] = min( n%3 == 0 ? dp[n/3] + 1 : MAXN,  n%2 == 0 ? dp[n/2] + 1 : MAXN, dp[n-1] + 1) 

그런데 여기서 pre[n]에 들어갈 후보가 n/3, n/2, n-1 이므로 최소값인 시점에 셋 중에 무엇인지를 알아야해서 

바로 min을 구하지 않고 비교를 해서 pr 을 구했다.

#include<bits/stdc++.h>

using namespace std;
int dp[1000004];
int pre[1000004];
int n;
int ret1, ret2, ret3;

int main(){
    cin >> n;

    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;
    pre[3] = 1;
    pre[2] = 1;
    pre[1] = 1;

    for(int i=4; i <= n; i++){
        ret1= 1000003, ret2 =1000003, ret3 = 1000003;
        int pr = 1000003;
        int minV = 1000003;
        
        if(i % 3 == 0){
           minV = dp[i/3] + 1;
           pr = i / 3;
        }
        if(i % 2 == 0){
            if(minV > dp[i/2] + 1){
                minV = dp[i/2] + 1;
                pr = i / 2;
            }
        }
        if(minV > dp[i-1] + 1 ){
            minV = dp[i-1] + 1;
            pr = i - 1;
        }
        pre[i] = pr;
        dp[i] = minV;
    }
    cout << dp[n] << "\n";
    cout << n << " ";
    while(n > 1){
        cout << pre[n] << " ";
        n = pre[n];
    }
    cout << "\n";
}