[백준] 11066. 파일 합치기 (DP/Java)

[백준] 11066. 파일 합치기

📌 풀이 과정

💡 문제 조건

• 여러 파일을 하나로 합치려면 한 번에 두 개씩만 합칠 수 있다.
• 두 파일(또는 그룹)을 합칠 때 비용 = 두 그룹의 크기 합
• 목표: 모든 파일을 합치는 최소 비용 구하기

ex) 파일 3개 [A, B, C]를 합치는 경우

• 방법 1: (A + B) 먼저 → (AB + C)
  • 총 비용 = (A + B) + (A + B + C)
• 방법 2: (B + C) 먼저 → (A + BC)
  • 총 비용 = (B + C) + (A + B + C)

 

1단계: DP 상태 정의

`dp[i][j]` = i번째부터 j번째 파일까지 모두 합치는 최소 비용

 

2단계: 점화식 도출

구간 [i, j]의 파일들을 합치려면

• 분할점 k에서 두 그룹으로 나눔: [i, k] + [k+1, j]
• 각각 따로 합친 후, 마지막에 두 그룹을 합쳐야 한다.

점화식:

dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j])
           (k는 i부터 j-1까지)

예시: dp[0][2] 계산

• k=0: [0] + [1,2] → `dp[0][0] + dp[1][2] + sum(0~2)`
• k=1: [0,1] + [2] → `dp[0][1] + dp[2][2] + sum(0~2)`

 

3단계: 계산 순서 (Bottom-up)

작은 구간부터 큰 구간 순으로 계산해야 한다.

이유: dp[0][2]를 계산할 때 dp[0][1], dp[1][2] 등이 이미 계산되어 있어야 하기 때문

계산 순서:

파일 1개: dp[0][0], dp[1][1], ... (모두 0)
파일 2개: dp[0][1], dp[1][2], dp[2][3], ...
파일 3개: dp[0][2], dp[1][3], ...
...
파일 K개: dp[0][K-1] ← 최종 답

 

✨ 제출 코드

메모리: 31388 KB

시간: 616 ms

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

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());

       while(T-- > 0){
          int K = Integer.parseInt(br.readLine());
          int[] sum = new int[K];

          // 누적합 계산
          StringTokenizer st = new StringTokenizer(br.readLine());
          for(int i = 0; i < K; i++){
             if(i == 0) sum[i] = Integer.parseInt(st.nextToken());
             else sum[i] = sum[i-1] + Integer.parseInt(st.nextToken());
          }

          int[][] dp = new int[K][K];
          
          // 파일 2개부터 K개까지 점진적으로 합치기
          for(int file = 2; file <= K; file++){
             // 현재 파일 개수에서 가능한 모든 시작점
             for(int start = 0; start <= K - file; start++){
                int end = start + file - 1;
                dp[start][end] = Integer.MAX_VALUE;
                
                // 모든 분할점에서 최솟값 찾기
                for(int k = start; k < end; k++){
                   // start부터 end까지의 합 계산
                   int cost = (start == 0) ? sum[end] : sum[end] - sum[start-1];
                   dp[start][end] = Math.min(dp[start][end], 
                                           dp[start][k] + dp[k+1][end] + cost);
                }
             }
          }
          
          System.out.println(dp[0][K-1]);
       }
    }
}