[BOJ/Java] 11066. 파일 합치기

📌 [BOJ/Java] 11066. 파일 합치기

🔗 문제 링크: 백준 11066번 - 파일 합치기

---

📖 문제 해석

📂 여러 개의 파일이 연속으로 놓여 있고, 이를 하나의 파일로 합치는 최소 비용을 구하는 문제이다.
💰 파일을 합치는 비용은 두 파일 크기의 합이며, 여러 번 합칠 경우 누적 비용이 증가한다.
🛠️ 파일을 합치는 순서를 잘 정해야 최소 비용이 된다.

🎯 핵심 개념:

• 파일을 어떤 순서로 합치는지가 중요하며, 최적의 순서를 찾기 위해 동적 계획법(DP)을 활용한다.

---

🛠️ 풀이 과정

1️⃣ 입력 처리 및 초기화

• K개의 파일 크기를 입력받고, **누적 합 배열(sum[])**을 만든다.
• dp[i][j]는 i번째 파일부터 j번째 파일까지 합치는 최소 비용을 의미한다.

2️⃣ DP 테이블 채우기

• 부분 파일들을 합치는 최소 비용을 구하는 점화식을 사용한다.
• dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1])
  (i부터 j까지 합치는 최소 비용을 찾기 위해, 중간 k를 기준으로 나누어 계산)

3️⃣ 최적의 파일 합치기 순서를 찾기

• 작은 구간부터 점차 큰 구간까지 최적의 해를 찾아간다.
• DP 테이블을 채운 후 dp[1][K] 값이 최소 비용이 된다.

---

💻 코드 구현 (Java)

import java.util.*;

public class Main {
    static int[][] dp;
    static int[] sum;
    static int K;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 테스트 케이스 개수

        while (T-- > 0) {
            K = sc.nextInt();
            int[] files = new int[K + 1];
            dp = new int[K + 1][K + 1];
            sum = new int[K + 1];

            for (int i = 1; i <= K; i++) {
                files[i] = sc.nextInt();
                sum[i] = sum[i - 1] + files[i]; // 누적합 배열
            }

            System.out.println(mergeFiles());
        }
    }

    public static int mergeFiles() {
        for (int len = 2; len <= K; len++) { // 부분 파일 길이 (2개 이상)
            for (int i = 1; i + len - 1 <= K; i++) { // 시작 인덱스
                int j = i + len - 1; // 끝 인덱스
                dp[i][j] = Integer.MAX_VALUE;

                for (int k = i; k < j; k++) { // 중간 지점 k
                    int cost = dp[i][k] + dp[k + 1][j] + (sum[j] - sum[i - 1]);
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }

        return dp[1][K]; // 전체 파일을 합치는 최소 비용
    }
}

---

⏱️ 시간 복잡도 분석

📌 O(K³) (최대 500³ = 약 1억 2500만 연산)
💡 dp[i][j]를 구하기 위해 중간 지점 k를 탐색해야 하므로 **O(K²) × O(K) = O(K³)**의 시간 복잡도를 가진다.
🔥 다행히 K ≤ 500이므로 적절한 DP 최적화 없이도 해결 가능하다.

---

💡 느낀점

✅ 최적 부분 구조를 이용한 동적 계획법(DP) 문제로,
부분 문제를 정의하고 점화식을 세우는 것이 핵심이었다.

✅ 누적 합 배열(sum[])을 사용하여 매번 부분 합을 구하지 않도록 시간을 단축할 수 있었다.

✅ 파일을 합치는 순서를 직접 정하는 게 아닌, DP로 최적의 해를 찾는 방식이 흥미로웠다! 🚀