[C++] 12852번 1로 만들기 2 - DP

#include <iostream>
#include <algorithm>

#define LOOP(i, N) for(int i=2; i<=N; i++)
#define MAX_N 1000001
#define INF 987654321

using namespace std;

int N;  //정수 N
int dp[MAX_N];  //DP
int bf[MAX_N];  //before

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    LOOP(i, N) {  //아래에서 부터 차근차근 올라가기
        dp[i]=dp[i-1]+1;
        bf[i]=i-1;
        
        if(!(i%2) && dp[i]>dp[i/2]+1) {
            dp[i] = dp[i/2]+1;
            bf[i]=i/2;
        }
        
        if(!(i%3) && dp[i]>dp[i/3]+1) {
            dp[i] = dp[i/3]+1;
            bf[i]=i/3;
        }
    }
    
    int i=N;
    
    cout << dp[N] << '\n';
    while(i) {
        cout << i << ' ';
        i=bf[i];
    }
    
    return 0;
}

전형적인 DP문제

 

작은 것 부터 천천히 키워나가면 된다.

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.