[백준] Silver I. 1로 만들기 2

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

 

사용 알고리즘

• 다이나믹 프로그래밍

 

풀이

 

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

public class Main {
    static int n;
    static int [] d = new int [1000002];
    static int[] path = new int[1000002];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        d[1] = 0;
        for(int i = 2; i <= n; i++) {
            d[i] = d[i-1] + 1;
            path[i] = i-1;

            if (i % 2 == 0 && d[i] > d[i/2] + 1) { // d[i-1]과 d[i/2]비교해서 d[i/2]가 더 작다면 최솟값을 할당
                d[i] = d[i/2] + 1;
                path[i] = i/2;
            }

            if (i % 3 == 0 && d[i] > d[i/3] + 1) {
                d[i] = d[i / 3] + 1;
                path[i] = i/3;
            }
        }

        System.out.println(d[n]);

        int cur = n;
        while(true) {
            System.out.print(cur + " ");
            if (cur == 1) break;
            cur = path[cur];
        }
        System.out.println();
    }
}

 

 

풀이

 

 

출처: https://141227.tistory.com/333

 

trace는 경로 값, 즉 그 전의 값을 저장하는 배열이다.

 

trace[2] = 1의 의미는 2에서 1로 가는게 최적이라는 의미다. 

 

d[10] 도달할 때의 최솟값을 살펴 보면,

d[9] + 1, dp[5] + 1 둘중에 하나여야 하는데 dp[9] + 1이 더 작으니 경로는 9가 된다.

 

dp[9]에서도 dp[8] + 1, dp[3] + 1을 계산하면 dp[3] + 1이 더 작으니 경로는 3이 된다.