[백준] 11066: 파일 합치기 - JAVA

04 Aug 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

파일을 1번부터 K번까지 합쳐야하는데 합치는 순서를 다르게 하여 최소 비용을 구해야 한다.

각 파일마다 비용을 입력받으면서 누적합으로 저장을 했다.(sum[5]는 1~5까지의 누적합)

dp배열을 만들어 저장을 하는데 dp[x][y]는 x~y까지 파일을 합치는 최소 비용을 갱신하며 저장한다.

x와 y의 차이를 gap으로 하여 gap을 1부터 늘려가면서 계산한다.

gap안에서 x와 y의 사이값d를 잡아 x~d, d+1~y의 합과 누적합배열에서 x~y를 찾아 최소비용을 갱신한다.

1~K를 나타내는 dp[1][K]가 답이된다.

---

메모리: 32180KB

시간: 552ms

언어: Java 11

코드

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));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            int K = Integer.parseInt(br.readLine());

            int[] sum = new int[K + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i < K + 1; i++) {
                sum[i] = sum[i - 1] + Integer.parseInt(st.nextToken());
            }

            int[][] dp = new int[K + 1][K + 1];
            for (int gap = 1; gap < K; gap++) {
                for (int i = 1; i <= K - gap; i++) {
                    int j = i + gap;
                    dp[i][j] = Integer.MAX_VALUE;

                    for (int d = i; d < j; d++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][d] + dp[d + 1][j] + sum[j] - sum[i - 1]);
                    }
                }
            }

            sb.append(dp[1][K]).append("\n");
        }

        System.out.println(sb);
    }

}