[Algorithm/Java][백준] 12852번 1로 만들기 2

[BOJ] 12852번 1로 만들기 2

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

접근 방법

처음에는 dfs 방법으로 재귀 함수를 이용해서 접근을 했는데 시간 초과가 나서
dp 방식으로 접근 방법을 바꾸었다.
dp[i]를 우선 dp[i-1] +1로 하고, 2로 나누어질 때와, 3으로 나누어질 때 dp[i/2] + 1과 dp[i/3] + 1을 비교해서 가장 작은 값을 dp[i]로 결정하였다.
i는 2부터 n까지 반복해서 dp[n]일 때 최솟값을 구하였고
만드는 절차를 출력하기 위해서 위에 했던 방식을 거꾸로 해서 출력해주었다.

Code

import java.util.Scanner;

public class BOJ12852 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for(int i = 2; i<=n; i++){
            dp[i] = dp[i-1] + 1;
            if(i%2 == 0){
                dp[i] = Math.min(dp[i], dp[i/2]+1);
            }
            if(i%3 == 0){
                dp[i] = Math.min(dp[i], dp[i/3]+1);
            }
        }
        System.out.println(dp[n]);
        StringBuilder sb = new StringBuilder();
        sb.append(n).append(" ");
        while(n>1){
            int min = dp[n-1];
            int temp = n-1;
            if(n%3 == 0 && dp[n/3] < min){
                min = dp[n/3];
                temp = n/3;
            }
            if(n%2 == 0 && dp[n/2] < min){
                min = dp[n/2];
                temp = n/2;
            }
            n = temp;
            sb.append(n).append(" ");

        }
        System.out.print(sb.toString().trim());
    }
}