백준, BOJ, 12582번 C++ [CPP]

DP의 전형적인 문제지만

DP의 과정도 출력한다고 해서.. 조금 출력을 고려해야하는 문제다.

 

 

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

 

---

 

#처음 맞는 풀이 - 수정 전

#include<iostream>

using namespace std;

int dp[1000001];

int num;

int main(){
    cin >> num;
    
    dp[1] = 0;
    dp[2] = 1;
    for(int i=3; i<=num; i++){
        dp[i] = dp[i-1]+1;
        if(i%2 == 0)dp[i] = min(dp[i],dp[i/2] + 1);
        if(i%3 == 0)dp[i] = min(dp[i],dp[i/3] + 1);
    }
    
    cout << dp[num] <<'\n';
    
    cout << num << " ";
    while(num != 1){
        int x,y,z;
        y = 99999;
        z = 99999;
        
        
        x = dp[num-1];
        if(num %2 == 0) y = dp[num/2];
        if(num %3 == 0) z = dp[num/3];
        
        int m = min(x,(min(y,z)));
        if(m == x) num = num-1;
        else if(m == y) num = num/2;
        else num = num/3;
        
        cout << num <<" ";
    }
    
    
}

 

물론 맞긴 맞았는데..

아래에 더 좋은 풀이가 있다.

 

#include<iostream>

using namespace std;

int dp[1000001];
int pre[1000001];

int num;

int main(){
    cin >> num;
    
    dp[1] = 0;
    dp[2] = 1;
    
    pre[1] = 0;
    pre[2] = 1;
    
    for(int i=3; i<=num; i++){
        dp[i] = dp[i-1]+1;
        pre[i] = i-1;
        
        if(i%2 == 0 && dp[i/2]+1 < dp[i]){
            dp[i] = dp[i/2] + 1;
            pre[i] = i/2;
        }
        if(i%3 == 0 && dp[i/3] + 1 < dp[i]){
            dp[i] = dp[i/3] + 1;
            pre[i] = i/3;
        }
    }
    
    cout << dp[num] <<'\n';
    
    while(num != 0){
        cout << num << " ";
        num = pre[num];
    }

    
    
}

 

복원 테이블을 따로 만들어서

과정을 추적하는 것이다.

 

솔직히 아래 것이 조금 더 낫다.

 

복원테이블을 만들어서 어디서 해당 숫자로 왔는지 저장하는 것이다.

그리고 1이 될 때까지 출력하면 끝!

 

DP는 진짜 답이 없다.

많이 풀어보는 것 밖에 답이 없다.