[백준] 12825. 1로 만들기 2

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

12852번: 1로 만들기 2

• n을 1로 만드는 가장 적은 연산 횟수를 구해서 출력하고, 이때 연산 과정까지 출력해야 한다.
• dp[i]: i를 1로 만드는 최소한의 연산 갯수
• record[i]: i를 1로 만드는 최소한의 연산 갯수의 과정에서, i가 되기 이전의 값
• 주의할 점은 dp[i]로 오는 경우가 여러개가 있을 수 있는데 (ex, dp[4] : 1 -> 2 -> 4, 1 -> 2 -> 3 -> 4), 기존 dp[i]의 값보다 새로운 dp[i]의 값이 작을 때만 갱신해주어야 한다.

import java.io.BufferedReader;
import java.io.IOException;

import java.io.InputStreamReader;

// 시간복잡도: O(N) = 10^6
public class Main {

    static int n;
    static int[] dp;
    static int[] record;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new int[n + 1];
        record = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            // 1 빼는 경우
            dp[i] = dp[i - 1] + 1;
            record[i] = i - 1;

            // 2로 나누는 경우
            if (i % 2 == 0) {
                if (dp[i] > dp[i / 2] + 1) {
                    dp[i] = dp[i / 2] + 1;
                    record[i] = i / 2;
                }
            }

            // 3으로 나누는 경우
            if (i % 3 == 0) {
                if (dp[i] > dp[i / 3] + 1) {
                    dp[i] = dp[i / 3] + 1;
                    record[i] = i / 3;
                }
            }
        }

        System.out.println(dp[n]);
        int idx = n;
        while (idx != 1) {
            System.out.print(idx + " ");
            idx = record[idx];
        }
        System.out.println("1");
    }
}