문제 - 1로 만들기2

문제접근

동적계획법이므로 점화식을 만든다.
1. 0,1인 경우에는 연산 사용횟수가 0이므로 설정을 해준다. => dp[0] = dp[1] = 0;
2. 그리고 1을 뺀 경우와 2로 나눈 경우, 3으로 나눈 경우를 각각 따로 생각해서 점화식을 만든다. 각각 따로 만드는 이유는 (if-elseX) 6인 경우를 생각해보자.
3. 점화식 : min(dp[i] ==d[i-1] +1,dp[i/2 or i/3] +1)
4. 이전에 했던 계산되었던 값들을 저장하기 위해서 trace배열을 따로만들어서 보관한다.

소스코드

import java.util.*;
import java.io.*;
public class Main {
    static int INF = 1_000_000;
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int dp[] = new int[INF+1];
        int trace[] = new int[INF+1];

        dp[1] = 0;

        for(int i=2; i<=N; i++){
            dp[i] = dp[i-1]+1;
            trace[i] = i-1;
            if(i%3 ==0 && dp[i] > dp[i/3]+1) {
                dp[i] = dp[i/3] +1;
                trace[i] = i/3;
            }
            if(i%2 ==0 && dp[i] > dp[i/2]+1) {
                dp[i] = dp[i/2] +1;
                trace[i] = i/2;
            }
        }

        System.out.println(dp[N]);
        StringBuilder sb = new StringBuilder();
        while(N>0){
            sb.append(N).append(" ");
            N = trace[N];
        }
        System.out.println(sb.toString());
    }
}