백준 11066번: 파일 합치기 (Java)

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

11066번: 파일 합치기

 

 

 

 

 

 

 

 

 

 

---

 

풀이

일반적인 구간 DP 문제입니다. dp[i][j]를 'i번째 파일부터 j번째 파일까지 합치는 최소 비용'이라고 하면,

dp[i][i+k] = min(dp[i][i+j]+ dp[i+j+1][i+k] + 'i번째 파일부터 j번째 파일의 용량')(for j in range(1, k))이 됩니다. 여기서 'i번째 파일부터 j번째 파일의 용량'은 누적합을 구하여 처리하면 됩니다.

 

배운 점

당연하지만, 책은 순서를 섞어서 합치면 안 됩니다: 카드 정렬하기처럼 풀려고 했는데 안 되길래, '뭐지?'하고 알고리즘 분류 'dp'를 보고 정신 차렸습니다. 커피+운동을 하니 열이 나서 정신이 없었나 봅니다. 실전에서 알고리즘 분류를 볼 수 있는 것이 아니기에, 정신 차리고 문제 풀어야겠습니다. 

 

코드

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());
        while (T-- > 0) {
            int ans = 0;
            int N = Integer.parseInt(br.readLine());
            int[] files = new int[N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                files[i] = Integer.parseInt(st.nextToken());
            }
            for (int i = 2; i <= N; i++) {
                files[i] += files[i-1];
            }
            int[][] dp = new int[N+1][N+1];
            for (int i = 1; i <= N; i++) {
                Arrays.fill(dp[i], 1_000_000_000);
                dp[i][i] = 0;
            }
            for (int k = 1; k < N; k++) {
                for (int i = 1; i <= N; i++) {
                    if (i+k > N) break;
                    for (int j = 0; j < k; j++) {
                        dp[i][i+k] = Math.min(dp[i][i+k], dp[i][i+j] + dp[i+j+1][i+k] + files[i+k] - files[i-1]);
                    }
                }
            }
            System.out.println(dp[1][N]);
        }
    }
 
}