백준 12852 - 1로 만들기 2

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

12852번: 1로 만들기 2

 

고려사항

• 동적 프로그래밍을 활용하면, 가작 작은 연산 수는 쉽게 구할 수 있다.
• 그 경로를 추적하는 것은 생각보다 어려웠다...
• 근데 그냥 똑같은 길이의 배열하나 더 만들어서 더 최소값이 나와서,
  v의 값이 갱신 될 때, 해당 값이 어떤 수에서 왔는지 path배열에 기록해주고
  1을 만날 때 까지 쫙 뽑아주면 되는 것이 었다..

 

#include <iostream>
#include <memory.h>
using namespace std;

int memo[1000001];
int path[1000001];

int dp(int num){
    int &v = memo[num];
    if(num == 1){
        v = 0;
        path[num] = num;
        return 0;
    }

    if(v != -1){
        return v;
    }

    v = dp(num-1) + 1;
    path[num] = num - 1;
    if(num % 2 == 0){
        if(v > dp(num/2)+1){
            v = dp(num/2)+1;
            path[num] = num/2;
        }
    }
    if( num % 3 == 0){
        if(v > dp(num/3)+1){
            v = dp(num/3)+1;
            path[num] = num/3;
        }
    }

    return v;
}

int main() {
    int n, cnt;

    cin>>n;
    memset(memo,-1, 1000001*4);

    cnt = dp(n);
    cout<<cnt<<"\n";

    while(n != 1){
        cout<<n<<" ";
        n = path[n];
    }
    cout<<1;

    return 0;
}