[백준] 12852 : 1로 만들기 2 (JAVA)

백준 온라인 저지의 12852번 문제, "1로 만들기 2"를 푸는 코드입니다. 문제는 자연수 N이 주어졌을 때, N을 1로 만들기 위한 최소 연산 횟수와 그 과정을 출력하는 것입니다. N을 1로 만들기 위해서는 다음 세 가지 연산 중 하나를 수행할 수 있습니다:

1. N에서 1을 뺀다.
2. N을 2로 나눈다. (N이 짝수인 경우)
3. N을 3으로 나눈다. (N이 3의 배수인 경우)

이 코드는 다이나믹 프로그래밍(Dynamic Programming) 알고리즘을 사용하여 문제를 해결합니다. 다음은 단계별 설명입니다.

1. 초기 설정:

• BufferedReader와 BufferedWriter를 사용하여 입력/출력 속도를 향상시킵니다. Java의 Scanner보다 효율적입니다.
• N: 입력으로 받는 자연수입니다.
• dp[i]: i를 1로 만들기 위한 최소 연산 횟수를 저장하는 배열입니다. dp[1] = 0으로 초기화됩니다. (1은 이미 1이므로 연산이 필요없음)
• path[i]: i를 1로 만들기 위한 과정에서 i 바로 이전의 수를 저장하는 배열입니다. 이는 최소 연산 과정을 역추적하기 위해 사용됩니다.

2. 다이나믹 프로그래밍:

• for 루프를 사용하여 2부터 N까지의 모든 수에 대해 최소 연산 횟수를 계산합니다.
• dp[i] = dp[i - 1] + 1; path[i] = i - 1;: 기본적으로 i에서 1을 빼는 연산을 고려합니다. 이는 항상 가능한 연산이며, 최소 연산 횟수의 상한선을 제공합니다.
• if (i % 2 == 0 && dp[i] > dp[i / 2] + 1): i가 짝수이고, i를 2로 나누는 것이 기존 최소 연산 횟수보다 적다면, dp[i]와 path[i]를 업데이트합니다.
• if (i % 3 == 0 && dp[i] > dp[i / 3] + 1): i가 3의 배수이고, i를 3으로 나누는 것이 기존 최소 연산 횟수보다 적다면, dp[i]와 path[i]를 업데이트합니다.

이 부분에서 다이나믹 프로그래밍의 핵심 아이디어인 최적 부분 구조 (Optimal Substructure)가 사용됩니다. 즉, i를 1로 만드는 최소 연산 횟수는 i/2 또는 i/3을 1로 만드는 최소 연산 횟수에 1을 더한 값과 비교하여 결정됩니다. 이미 계산된 dp[i/2]와 dp[i/3]의 값을 활용하여 효율적으로 최소 연산 횟수를 구합니다.

3. 결과 출력:

• bw.write(dp[N]): N을 1로 만들기 위한 최소 연산 횟수를 출력합니다.
• for 루프를 사용하여 path 배열을 역추적하여 최소 연산 과정을 출력합니다. path[index]는 현재 수 index의 이전 수를 가리키므로, index를 path[index]로 계속 업데이트하면 1까지의 과정을 역순으로 얻을 수 있습니다.

알고리즘 특징 및 장단점:

• 장점: 다이나믹 프로그래밍을 사용하여 효율적으로 최소 연산 횟수와 과정을 구합니다. 시간 복잡도는 O(N)입니다.
• 단점: 메모리를 O(N)만큼 사용합니다. N이 매우 큰 경우 메모리 제한에 걸릴 수 있습니다. 하지만 이 문제의 제한된 N의 크기에서는 문제가 되지 않습니다.

코드:

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

public class b12852 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine()), dp[] = new int[N + 1], path[] = new int[N + 1];
        // dp[i]: i를 1로 만드는 최소 연산 횟수
        // path[i]: i를 1로 만드는 과정에서 i 바로 이전의 수

        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1; // 기본적으로 1을 빼는 연산
            path[i] = i - 1;       // 이전 수는 i-1

            if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) { // 2로 나누는 연산이 더 효율적인 경우
                dp[i] = dp[i / 2] + 1;
                path[i] = i / 2;
            }
            if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) { // 3으로 나누는 연산이 더 효율적인 경우
                dp[i] = dp[i / 3] + 1;
                path[i] = i / 3;
            }
        }

        bw.write(dp[N] + "\n"); // 최소 연산 횟수 출력
        for (int index = N; index > 0; index = path[index]) { // 최소 연산 과정 역추적 및 출력
            bw.write(index + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}