[BOJ 11066] 파일 합치기 (Java)

BOJ 11066 파일 합치기

난이도 : 골드 3

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

11066번: 파일 합치기

 

전략

행렬 곱셈 순서 문제와 비슷한 유형이다.

 

i ~ j까지의 파일을 합치는 최소 비용을 dp[i][j]로 하여 갱신시켜야 한다.

 

구하고자 하는 목표는 dp[1][K] 이므로 작은 문제부터 차근차근 올라오면 풀 수 있다.

 

a ~ b 파일의 크기 합이 sum(a, b)라면 dp[i][j]는 다음과 같이 유도할 수 있다.

 

dp[i][i] = 0

dp[i][j] = min { dp[i][k] + dp[k+1][j] + sum(i, k) + sum(k+1, j) }

                      ( i <= k < j )

 

구간합 sum(a, b)는 누적 합을 이용해 O(1)에 계산할 수 있었다.

 

시행착오

구간 합 구하기에서 반대로 뺄셈을 진행한 실수를 했었다.

 

코드

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

public class Main {

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

        for (int t = 0; t < T; t++) {
            int K = Integer.parseInt(br.readLine());
            int[] file = new int[K + 1];
            int[] prefixSum = new int[K + 1];
            int[][] dp = new int[K + 1][K + 1];

            int sum = 0;
            String[] line = br.readLine().split(" ");
            for (int i = 0; i < K; i++) {
                file[i + 1] = Integer.parseInt(line[i]);
                sum += file[i + 1];
                prefixSum[i + 1] = sum;
            }

            for (int i = K; i >= 1; i--) {
                for (int j = i; j <= K; j++) {
                    dp[i][j] = Integer.MAX_VALUE;
                    if (i == j)
                        dp[i][j] = 0;
                    else {
                        for (int k = i; k <= j - 1; k++) {
                            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + getSum(prefixSum, i, k) + getSum(prefixSum, k + 1, j));
                        }
                    }
                }
            }

            System.out.println(dp[1][K]);
        }
    }

    static int getSum(int[] sum, int s, int e) {
        return sum[e] - sum[s - 1];
    }
}

 

깨달은 점

행렬 곱셈 순서 풀 때 dp 진행 순서가 헷갈렸었는데

이번에 복습 느낌으로 하면서 확실히 익힌 것 같다.