[백준] 11066번 파일 합치기

문제 설명

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

문제 풀이

• 처음엔 순서를 마음대로 정할 수 있는 줄 알고 그리디 알고리즘으로 접근했으나 각 파일의 순서는 변경할 수 없어 다이나믹 프로그래밍으로 풀이하였다.
• 문제 풀이에 사용된 점화식은 아래와 같다.

- DP[from][to] : from 인덱스에서 to 인덱스까지 파일 합치기 최소 비용 리턴
- sum[from][to] : from 인덱스에서 to 인덱스까지 파일 크기 총합
- DP[from][to] = MIN(DP[from][i] + DP[i+1][to] + sum[from][to]) (from <= i < to)

소스 코드 (JAVA)

import java.io.*;


public class Main {
    public static int T, K;
    public static int INF = 987654321;
    public static int[] arr = new int[500];
    public static int[][] dp = new int[500][500];
    public static int[][] sumArr = new int[500][500];
    
    public static void init() {
        for (int i = 0; i < K; i++) {
            int tmpSum = 0;
            for (int j = 0; j < K; j++) {
                if (j >= i) tmpSum += arr[j];
                dp[i][j] = INF;
                sumArr[i][j] = tmpSum;
            }
        }
    }

    //from부터 to까지의 파일합치기 합의 최솟값 출력
    public static int solve(int from, int to) {
        //기저 조건
        if (from == to) return 0;
        if (dp[from][to] != INF) return dp[from][to];
        int result = INF;
        for (int i = from; i < to; i++) {
            result = Math.min(result, sumArr[from][to] + solve(from, i) + solve(i+1, to));
        }
        return dp[from][to] = result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            K = Integer.parseInt(br.readLine());
            String[] input = br.readLine().split(" ");
            for (int i = 0; i < K; i++) {
                arr[i] = Integer.parseInt(input[i]);
            }
            init();
            bw.write(solve(0, K-1) + "\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }
}