[백준 12852번] 1로 만들기 2(C++ , DP)

이전에 1로 만들기 1을 풀었던 터라, 그대로 가져와서 백트레킹만 구현해서 제출했다.

 

 

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
int dp[1000001];
vector<int> v;
int main(void)
{

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N,cnt =0;
    cin >> N;
    dp[1] = 0; //1부터 시작해서 
    
    for(int i = 2; i<=N ; i++) // 2, 3, ... N까지 
    {
        if( i%3 == 0 && i%2 == 0)
        {
        	// 3으로 나눈거 +1, 2로 나눈거 +1, 한칸 전에꺼 +1중 가장 작은거
            dp[i] = min(dp[i/3]+1, min(dp[i/2]+1, dp[i-1]+1)); 
        }
        else if( i%3 ==0 && i%2 != 0)
        {
        	// 2로 못나눌때, 3으로 나눈거 +1, 한칸 전꺼 +1중 작은거
            dp[i] = min(dp[i/3]+1, dp[i-1]+1);
        }
        else if( i%3 != 0 && i%2 ==0)
        {
        	//3으로 못나눌때, 2로 나눈거+!, 한칸 전꺼 +1 중 작은거.
            dp[i] = min(dp[i/2]+1, dp[i-1]+1);
        }
        else {
        	// 아무것도 못나눌때, 한칸 전꺼 +1
            dp[i] = dp[i-1]+1;
        }
    }
    //횟수 출력하고 
    cout << dp[N] << endl;
    
    //다시 돌아와봄.
    v.push_back(N); // N부터 시작해서
    for(int i = dp[N]; i>=1; i--) // 횟수만큼 반복.
    {
    	// N이 3으로 나눠지고, 3으로 나눈 값이 현재 횟수 -1과 같다면.
        if(N%3==0 && dp[N/3] == i-1) 
        {
            v.push_back(N/3);
            N=N/3;
        }
        // N이 2로 나눠지고, 2으로 나눈 값이 현재 횟수 -1과 같다면.
        else if(N%2 == 0 && dp[N/2] == i-1)
        {
            v.push_back(N/2);
            N = N/2;
        }
        //나머지 경우들.
        else{
            v.push_back(N-1);
            N = N-1;
        }
    }
    for(int i = 0 ; i< v.size(); i++)
    {
        cout << v[i]<<" ";
    }

}