BOJ - 1로 만들기 2(12852)

실버1 : 동적 계획법 문제이다.

생각

전형적인 dp 문제이다. 다만 이 문제는, 경로를 추적해야 한다는 점에서 조금 다르다. 경로를 추적하는 방법으로는 dp를 미리 구해놓고, 이것을 역으로 추적하여 구하는 방법이 가장 간단하다.

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<cmath>
#include<functional>
using namespace std;
int N;
int dp[1000001];
vector<int> trace;
 
void tracing(int num){
    trace.push_back(num);
    if (num == 1) return;
    int before = num-1;
    if (num%3 == 0) {
        if (dp[before] > dp[num/3]) before = num/3;
    }
    if(num%2 == 0) {
        if (dp[before] > dp[num/2]) before = num/2;
    }
    tracing(before);
}
 
int main(){
    cin >> N;
    dp[0] = 987654321;
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i-1] + 1;
        if (i%3 == 0) {
            dp[i] = min(dp[i], dp[i/3]+1);
        }
        if (i%2 == 0){
            dp[i] = min(dp[i], dp[i/2]+1);
        }
    }
    tracing(N);
 
    cout << dp[N] << endl;
    for (int i = 0; i < trace.size(); i++) {
        cout << trace[i] << ' ';
    }
 
    return 0;
}

Reference

• 백준(12852번) - 1로 만들기 2