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

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

11066번: 파일 합치기

 

문제 

N 개의 파일이 주어졌을 때, 

파일을 어떠한 순서로 조합했을 때 가장 최소의 값으로 합칠 수 있는지 구하는 문제

---

풀이

다이나믹 프로그래밍 

 

점화식

dp[i][j] = i 번째 파일부터 j 번째 파일 까지를 합쳤을 때의 최소값 

 

dp[i][j] = dp[i][k] + dp[k+1][j] + sum[i][j] ( 마지막에 모든 파일 값을 더하기 때문에 sum 은 항상 들어감 )

3중 루프를 돌려 

i 와 j 사이의 k 를 증가시키면서 최소값을 찾는다. 

 

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

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(reader.readLine());
        
        for(int l = 0; l<tc; l++) {
            int n = Integer.parseInt(reader.readLine());
            String[] tmp = reader.readLine().split(" ");
            
            int[] sum = new int[n];
            
            for(int j = 0; j<n; j++) {
                if (j == 0) {
                    sum[j] = Integer.parseInt(tmp[j]);
                    continue;
                }
                sum[j] = sum[j-1] + Integer.parseInt(tmp[j]);
            }
            
            /* dp */
            int[][] dp = new int[n][n];
            
            // dx ~ dy 까지의 최소 비용
            for(int i = 1; i<n; i++) {
                for(int dx = 0; dx+i<n; dx++) {
                    int dy = dx+i;
                    dp[dx][dy] = Integer.MAX_VALUE;
                    
                    // k를 기준으로 왼쪽과 오른쪽으로 나누어서 최소값을 찾는다.
                    for(int k = dx; k<dy; k++) {
                        int s = dx == 0 ? 0 : sum[dx-1];
                        dp[dx][dy] = Math.min(dp[dx][k] + dp[k+1][dy] + sum[dy] - s, dp[dx][dy]);
                    }
                }
            }
            System.out.println(dp[0][n-1]);
        }
    }
}