[Java] 1로 만들기 2 Silver 1

문제 링크

이 문제는 N을 1로 만드는 방법에 포함되어 있는 수의 출력까지 요구하고 있다.

N을 1로 만드는 최소 횟수만 출력하라고 했으면, BFS로 쉽게 풀 수 있었을 거 같은데 만드는 방법도 출력하라고 하니까 고민을 좀 해봐야 할 거 같다.

어제 고생한 기억을 교훈 삼아 바로 아이패드를 꺼냈다~..

최솟값만 구하려면 이렇게 바로 할 수 있다.

점화식은 이렇다.

dp[i] = MIN(dp[i-1], dp[i/2], dp[i/3])

이렇게 모든 i에 대해서 2부터 N까지 최솟값을 갱신해주면, 시간 복잡도가 O(N)이라서 시간초과가 발생하지 않는다!

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // dp
        int[] dp = new int[N + 1];
        for (int i = 2; i <= N; i++) {
            dp[i] = Math.min(dp[i - 1], Math.min(dp[i / 2], dp[i / 3])) + 1;
        }

        // 출력
        System.out.println(dp[N]);
    }
}

그런데 우리는 경로도 구해야한다..

그러면 매번 어떤 값이 채택된 것인지를 명확히 알아야 하기에 if 문을 통해서 세 가지 케이스를 모두 각각 따져봐야 한다.

그리고 path를 저장할 배열을 추가해서 최솟값일 때 경로를 저장한다!

그리고 당연히 경로도 저장하면 된다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // 배열 생성
        int[] dp = new int[N + 1];
        int[] path = new int[N + 1];

        // 배열 초기화
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[1] = 0;

        // DP
        for (int i = 2; i <= N; i++) {

            // dp[i]는 항상 MAX_VALUE로 채워져있음!
            dp[i] = dp[i - 1] + 1;
            path[i] = i - 1;

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

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


        // 출력
        System.out.println(dp[N]);
        System.out.print(N + " ");
        while (N != 1) {
            System.out.print(path[N] + " ");
            N = path[N];
        }
    }
}

실제로 디버깅 해보면 각각 dp, path 배열인데 제대로된 값이 나온다!