[BOJ] 11066: 파일 합치기(JAVA)

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

11066번: 파일 합치기

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.

소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.

입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

예제 입력 1 

2

4

40 30 30 50

15

1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

예제 출력 1 

300

864

 

---

[문제 풀이]

다른 사람들의 풀이를 보고도 잘 이해가 되지 않았던 문제였다. 

DP를 이용하여 해결하는 문제였는데 값을 어떤 규칙을 가지고 저장해야할 지 헤맸던 것 같다.

비용을 2차원 정수 배열 cost에 저장할 것이고 i번째 장부터 j번째 장까지 합치는 비용을 cost[i][j]에 저장할 것이다.

그러면  cost[i][i+j] = Math.min(cost[i][i+j], cost[i][k]+cost[k+1][i+j]+sum[i+j]-sum[i-1]) 의 공식이 성립하게 된다.

 

여기까지는 괜찮았는데 다음 과정 부터 이해가 조금 어려웠다.

 

cost[i][i+1]의 값은 i번째 장부터 i+1번째 장, 즉 바로 다음 장과 합치는 경우의 비용이기 때문에 

cost[i][i+1] = files[i]+files[i+1]; 의 값을 대입한다.

 

그 다음 3번 중첩된 반복문을 거쳐 비용을 계산할 것이다.

1. 가장 바깥쪽 for문의 j변수는 장 사이의 gap을 의미

    ex) gap=2라면, cost[i][i+2] 의 값을 계산, 즉 i번째 책부터 i+gap번째 장까지 합치는 비용

 

2. 그 안쪽 for문의 i변수는 합치기 시작할 장 번호

 

3. 가장 안쪽 for문의 k변수는 i와 i+j 사이의 값으로, 합치기 시작할 장과 합칠 마지막 장 사이의 장 번호라고 생각하면 된다.

    3-1. 해당 반복분 안에서 가장 먼저 검색해야 할 것은 cost[i][i+j]가 0인지 아닌지이다. 해당 비용이 0이면 아직 아무런 계산도 하지 않은 것이므로 기존 값과 새로운 값을 비교해 더 작은 값을 넣어주면 계속 0이 될 것이다. 따라서 이 때는 min값을 찾는 것이 아니라,

          3-1-1. i가 0보다 크다면, cost[i][i+j] = cost[i][k]+cost[k+1][i+j]+sum[i+j]-sum[i-1];

          3-1-2. i가 0이면, cost[i][i+j] = cost[i][k]+cost[k+1][i+j]+sum[i+j];

          으로 값을 대입한다. 예를 들어 i가 1, j가 2었다면, cost[1][3] = cost[1][1] + cost[2][3] + sum[3] - sum[1]; 이 된다. + sum[3] - sum[1]   해당 수식을 계산하는 이유는 sum[3]은 1장부터 3장까지 모두 합치는 경우의 값인데, cost[1][1] + cost[2][3] 은 1장~3장을 모두 합친게 아니라, 1장은 두고, 2장~3장을 합친 경우이므로, 1장을 합친 경우의 값은 빼주어야 한다. 따라서 -sum[1]을 해준 것이다.

          

    3-2. cost[i][i+j]가 0보다 크고,

          3-2-1. i가 0보다 크다면, cost[i][i+j] = Math.min(cost[i][i+j], cost[i][k]+cost[k+1][i+j]+sum[i+j]-sum[i-1]);

          3-2-2. i가 0이면, cost[i][i+j] = Math.min(cost[i][i+j], cost[i][k]+cost[k+1][i+j]+sum[i+j]);

          으로 더 작은 값을 cost[i][i+j]에 대입한다.

 

4. cost를 모두 구하고 나면 1장부터 K장까지 모두 합쳤을 때의 최소 비용을 구하는 것이므로 cost[0][K-1]을 반화하면 된다.

 

[코드]

import java.util.*;

public class Main{
   static int[] sum;
   public static int dp(int[] files) {
      int[][] cost = new int[files.length][files.length];
      for(int i=0;i<files.length-1;i++) {
         cost[i][i+1]=files[i]+files[i+1];
     }

     for(int j=2;j<files.length;j++) {
       for(int i=0;i+j<files.length;i++) {
         for(int k=i;k<i+j;k++) {
           if(cost[i][i+j]==0) {
              if(i>0)
               cost[i][i+j] = cost[i][k]+cost[k+1][i+j]+sum[i+j]-sum[i-1];
             else
               cost[i][i+j] = cost[i][k]+cost[k+1][i+j]+sum[i+j];

           }
           else {
             if(i>0)
               cost[i][i+j] = Math.min(cost[i][i+j], cost[i][k]+cost[k+1][i+j]+sum[i+j]-sum[i-1]);
             else
               cost[i][i+j] = Math.min(cost[i][i+j], cost[i][k]+cost[k+1][i+j]+sum[i+j]);

           }
         }
       }
     }

     return cost[0][files.length-1];
   }
    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int T = sc.nextInt();
         StringBuilder sb = new StringBuilder();
         for(int i=0;i<T;i++) {
            int K = sc.nextInt();
            int[] files = new int[K];
            sum = new int[K];
            for(int j=0;j<K;j++) {
               files[j] = sc.nextInt();
               if(j>0)
                 sum[j]= sum[j-1]+files[j];
               else
                 sum[j] = files[j];
            }
            sb.append(dp(files)).append("\n");
         }
         System.out.println(sb.toString());
         
    }
}