파일 합치기 문제 (Knuth Optimization 활용)

문제 설명

김대전은 소설을 여러 개의 장으로 나누어 파일에 저장한다. 그는 모든 파일을 하나로 합치려 하는데, 두 개의 파일을 합칠 때 드는 비용은 두 파일의 크기의 합이다.
각각의 장들이 수록된 파일 크기가 주어졌을 때, 최소 비용으로 모든 파일을 합치는 방법을 찾아야 한다.

예를 들어 파일 크기가 [40, 30, 30, 50]인 경우:

• 파일을 합치는 순서에 따라 비용이 달라진다.
• 최소 비용을 구하는 최적의 방법을 찾는 것이 목표이다.

제약 조건:

• ( 3 \leq K \leq 5,000 ) (파일의 개수)
• 파일 크기는 ( 10,000 ) 이하의 양의 정수
• 테스트 케이스 개수 ( T )가 주어지며, 각 테스트 케이스마다 독립적으로 계산해야 한다.

코드

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

public class Main {

    public static void solve(int n, int[] v) {
        int[][] dp = new int[n + 1][n + 1];
        int[][] K = new int[n + 1][n + 1];
        int[] s = new int[n + 1];

        // Prefix sum 계산
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + v[i];
        }

        // 초기화
        for (int i = 1; i <= n; i++) {
            dp[i - 1][i] = 0;
            K[i - 1][i] = i;
        }

        // DP와 Knuth Optimization
        for (int m = 2; m <= n; m++) {
            for (int i = 0; i + m <= n; i++) {
                int j = i + m;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = K[i][j - 1]; k <= K[i + 1][j]; k++) {
                    int cost = dp[i][k] + dp[k][j] + s[j] - s[i];
                    if (dp[i][j] > cost) {
                        dp[i][j] = cost;
                        K[i][j] = k;
                    }
                }
            }
        }

        System.out.println(dp[0][n]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[] v = new int[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                v[i] = Integer.parseInt(st.nextToken());
            }
            solve(n, v);
        }
    }
}

코드 설명

1. 입력 처리

• 각 테스트 케이스마다 파일의 수 𝑛과 각 파일의 크기를 입력받는다.
• v 배열: 파일 크기 저장 (1-based 인덱스 사용).

2. Prefix Sum 계산

• s[i]: 파일 1부터 𝑖까지의 합을 저장한다.
• 이를 통해 두 구간의 합을 𝑂(1)시간에 계산할 수 있다.

for (int i = 1; i <= n; i++) {
    s[i] = s[i - 1] + v[i];
}

3. DP 테이블 초기화

• dp[i][j]: 파일 𝑖부터 𝑗까지 합치는 데 드는 최소 비용.
• 초기 상태에서 𝑖=𝑗인 경우는 비용이 0이다.

for (int i = 1; i <= n; i++) {
    dp[i - 1][i] = 0;
    K[i - 1][i] = i;
}

4. Knuth Optimization 적용

• DP를 효율적으로 풀기 위해 𝐾[𝑖][𝑗]를 사용한다.𝑑𝑝[𝑖][𝑗]를 계산할 때 𝐾[𝑖][𝑗−1]부터 𝐾[𝑖+1][𝑗]사이의 𝑘만 탐색한다.

for (int m = 2; m <= n; m++) {
    for (int i = 0; i + m <= n; i++) {
        int j = i + m;
        dp[i][j] = Integer.MAX_VALUE;
        for (int k = K[i][j - 1]; k <= K[i + 1][j]; k++) {
            int cost = dp[i][k] + dp[k][j] + s[j] - s[i];
            if (dp[i][j] > cost) {
                dp[i][j] = cost;
                K[i][j] = k;
            }
        }
    }
}

5. 출력

• 각 테스트 케이스에 대해 최소 비용 dp[0][n]를 출력한다.

핵심 개념: Knuth Optimization

• Knuth Optimization은 DP 최적화 기법 중 하나이다.
• dp[i][j]를 계산할 때, 특정 구간에서 𝑘의 범위를 줄여 시간 복잡도를 개선한다.
• 이 문제의 시간 복잡도는 𝑂(𝑛2)이며, 일반적인 DP 방식보다 효율적이다.

So...

이 문제는 파일을 합칠 때 발생하는 비용을 최소화하는 최적화 문제로, DP와 Knuth Optimization을 활용해 해결한다.
처음에는 DP만으로 문제를 풀었으나, 𝑂(𝑛3) 시간 복잡도로는 큰 입력을 처리할 수 없었다.
Knuth Optimization을 적용해 효율성을 극대화했으며, 문제 해결에 대한 논리적 최적화의 중요성을 다시금 느꼈다.