[알고리즘 TIL] 11066. 파일 합치기 (***)

문제

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

설명

이 문제는 여러 개의 파일을 순서대로 합칠 때, 최소 비용을 구하는 문제이다. 연속된 파일들만 합칠 수 있다는 점에서 동적 계획법이라는 힌트를 얻을 수 있다.

📌 동적 계획법이란?
동적 계획법이란 부분 문제를 정의하여 하위 문제를 풀고, 그 결과를 기억해 이용하는 알고리즘이다.
즉, 점화식을 도출하여 결과를 저장하고 이용한다는 것이 특징이다.

 

먼저, 작은 입력부터 생각해보자.

• 만약 1개의 파일이라면? 비용이 들지 않으므로 0이다.
• 만약 2개의 파일 f1, f2라면? 그냥 f1+f2 이다.
• 파일이 3개라면? (f1+f2)+f3 또는 f1+(f2+f3)의 비용 중 낮은 비용을 고를 것이다.
• 아직 잘 모르겠다.. 만약 파일이 4개라면? 다음의 경우 중 최소 비용을 고르면 된다.
  • f1+(f2+(f3+f4))
  • (f1+f2)+(f3+f4)
  • ((f1+f2))+f3)+f4

• 파일이 n개일 경우 최소 비용은 ..
  • f1+(f2~fn의 합의 최소비용)
  • (f1+f2)+(f3~fn의 합의 최소비용)
  • ...
  • (f1~fn-1의 합의 최소비용)+fn

dp[i][j] = i~j까지 파일을 합쳤을 때 최소 비용이라고 하자. 

그럼, dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))라고 점화식을 세울 수 있다! 

*마지막에는 누적합을 더해줘야함.

구현

import java.io.*;

public class Q11066_파일합치기_DP {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int K = Integer.parseInt(br.readLine());
            int[] files = new int[K + 1];//파일 크기 저장
            int[][] dp = new int[K + 1][K + 1]; //최소 비용 저장
            int[] sum = new int[K + 1]; //파일 크기 누적합

            //파일 크기 입력 및 누적합 계산
            for (int i = 1; i <= K; i++) {
                files[i] = Integer.parseInt(br.readLine());
                sum[i] = sum[i - 1] + files[i];
            }

            //DP 실행
            for (int length = 2; length <= K; length++) { //파일 크기가 2인 경우부터 시작
                for (int i = 1; i <= K - length + 1; i++) {
                    //i는 구간 시작점, j는 구간 끝점
                    int j = i + length - 1;
                    dp[i][j] = Integer.MAX_VALUE;

                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j]-sum[i-1]);
                    }
                }
            }

            //최종 결과 출력
            bw.write(dp[1][K]+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}