[DP] [백준 / 12852] 실버 1 - 1로 만들기 2 (java/자바)

비슷한 문제
[DP] [백준 / 1699] 실버 2 - 제곱수의 합 (java/자바)
[BFS / DFS] [백준 / 1697 ] 실버1 - 숨바꼭질 (java/자바)

문제

접근

7에서 1까지의 최소 연산을 DP로 구할 수있다.
예를들어 7을 넣으면 6의 최소연산 + 1 과 같다.
그리고 6의 최소연산은 2의 최소연산 +1 과 같다.
2의 최소연산은 1과 같다.
따라서 7의 최소연산은 3이고, 7 -> 6 -> 2 -> 1 임을 알 수 있다.

(참고) BFS로도 구할 수 있는 문제기도 하다.

성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(r.readLine());
        int[] dp = new int[N + 1];
        int[] trace = new int[N + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[1] =0;
        for(int i=2; i<N+1; i++){
            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;
            }
            if(i-1>0 && dp[i] > dp[i-1] +1){
                dp[i] = dp[i-1] +1;
                trace[i] = i-1;
            }
        }
        System.out.println(dp[N]);
        int num = N;
        for(int i=0; i<=dp[N]; i++){
            System.out.print(num + " ");
            num = trace[num];
        }

    }
}

손으로 디버깅