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

 

문제

숫자 N이 주어지고, 가능한 연산은 3가지가 주어진다.

3으로 나누어 떨어진다면 3으로 나누기, 2로 나누어 떨어진다면 2로 나누기, 1을 빼기.

이 때 최소의 연산 횟수로 1을 만든다고 할 때 최소 연산 횟수와 해당 경우에 사용되는 숫자를 출력하는 문제.

 

 

풀이

기존의 '1로 만들기' 문제에서 사용되는 숫자를 출력하는 로직만 넣어주면된다고 생각했다.

처음엔 MAP 자료구조를 이용해서 DP의 인덱스 값을 KEY로 해당 인덱스를 만들어주기 위한 숫자들을 VALUE로(ArrayList)로 저장하게끔 했다. 통과는 했다.

하지만 다른 분들의 답안을 보고 int 배열을 둔 뒤 재귀 호출로 출력하는 방식이 있다는 것을 발견했다.

처음에 푼 풀이보다 시간이 10분의 1로 줄어들었다. 

 

 

코드

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

public class b12852 {

    // map을 사용해서 이전 시행 인덱스의 list값들을 현재 시행 인덱스에 add해주고 나의 인덱스로 add
    static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int X = Integer.parseInt(br.readLine());
        int[] dp = new int[X + 1]; // 0: 0, 1:0, 2:1, 3:1
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = dp[1] = 0;

        HashMap<Integer, ArrayList<Integer>> nums = new HashMap<>();
        for (int i = 1; i <= X; i++) {
            nums.put(i, new ArrayList<>());
            nums.get(i).add(i);
        }

        for (int i = 2; i <= X; i++) {
            int min = 1;

            if (i % 3 == 0) {
                dp[i] = dp[i / 3] + 1;
            }
            if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
                dp[i] = dp[i / 2] + 1;
                min = 2;
            }
            if (dp[i - 1] + 1 < dp[i]) {
                dp[i] = dp[i - 1] + 1;
                min = 3;
            }

            switch (min) {
                case 1:
                    for (Integer num : nums.get(i / 3)) {
                        nums.get(i).add(num);
                    }
                    break;
                case 2:
                    for (Integer num : nums.get(i / 2)) {
                        nums.get(i).add(num);
                    }
                    break;
                case 3:
                    for (Integer num : nums.get(i - 1)) {
                        nums.get(i).add(num);
                    }
            }
        }

        sb.append(dp[X]).append('\n');
        for (Integer num : nums.get(X)) {
            sb.append(num).append(' ');
        }
        System.out.println(sb);
    }

    // 다이나믹 프로그래밍 + DFS
    static StringBuilder sb;
    static void solution2() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1]; // 0:0, 1:1, 2:1, 3:1
        int[] prev = new int[N + 1];

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

        sb.append(dp[N]).append('\n');
        dfs(N, prev);
        System.out.println(sb);
    }

    static void dfs(int n, int[] prev) {
        if (n == 0)
            return;
        sb.append(n).append(' ');
        dfs(prev[n], prev);
    }

    public static void main(String[] args) throws IOException {
        solution2();
    }
}