[ Baekjoon - 11/22 ] - 11066번: 파일 합치기

문제 링크 : https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

 

소요 시간 : 2시간 반

파일 합치기 

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	23481	12040	7994	50.157%

문제

소설가인 김대전은 소설을 여러 장(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

 

 

1.  문제를 읽고 이해하기

▶ 입출력 형태 및 조건

       1         >  T (테케, T : [1, ]) 

 T번 반복   >  K (소설을 구성하는 장의 수 : [3, 500]) 

 T번 반복   >  Ki (1장부터 K장까지 수록한 파일의 크기, Ki : [1, 10,000]) 

출력 > 모든 장을 합치는데 필요한 최소비용을 출력

 

 

▶ 문제

파일과 파일을 합쳐 임시파일을 만들어 나갈 수 있는데,

임시파일을 만드는 비용은 이 임시파일을 만들기 위해 전에 두 파일의 비용을 합한 값이다.

이 때 전체 비용의 최솟값을 출력하는 문제임.

 

※ 인접한 파일만 합칠 수 있다는 점을 주의해야한다

[ 문제에서 언급한 바 : 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고 ]

 

 

▶ 시간, 메모리 제한 :2초, 256MB

 

2.  문제를 익숙한 용어로 재정의와 추상화

어떤 형식으로 이루어질지 간단히 그려보았다. 밑의 트리를 그릴 때 dp를 어떻게 잡아야할지 좀 난해해졌음 후ㅠ

 

3.  문제 해결 방안

1st 접근 ) dp 2차원배열 - dp[ i ][ j ] : ( i ~ j )페이지 합의 최솟값 ver1

가장 처음에 문제를 대충읽고 이거 그리디문제 아닌가 했었지만, 가장 작은 페이지부터 합친다고 정답이 되는 것이 아니었음을 깨닫고 DP로 생각을 돌렸다.

※ 왜냐하면, 인접한 파일끼리만 합칠 수 있기 때문에 순서를 고려하여 생각을 해야하기 때문임

 

dp를 2차원 배열로 잡고 i~j페이지 합의 최솟값을 구해보기 위해 처리 방식을 고민해보았는데

해당 칸으로는 부족하다는 생각이 들어서 포기했음..

=> 해당 칸이 누적된 값인지, 단일값인지 구분도 어렵고 연산식도 복잡했기 때문

 

2nd 접근 ) dp 2차원배열 - dp[ i ][ j ] : ( i ~ j )페이지 합의 최솟값 ver2

우선 인접한 파일만 합칠 수 있기 때문에 이를 빠르게 연산할 수 있도록 누적합 배열을 하나 만들어준다.

 

4개의 장을 합치는 경우를 생각해보자.

ex) a~d를 합치는 경우

(b+c+d) + (a+b+c+d) / (a+b) + (c+d) + (a+b+c+d) / (a+b+c) + (a+b+c+d)

위 세가지중 최솟값이 답이됨

bc) 인접한 값만 더해야하므로 위 세가지 경우가 아니면 불가능

 

최종 dp의 형태는 다음과 같다.

1) DP[i][i] = 0 (K<2)
2) DP[i][i+1] = V[i] + V[i+1] (K>2)
3) DP[i][j] = MIN(DP[i][k]+DP[k+1][j]+SUM(V[i~j])

4.  위 계획 검증

i부터 j까지 합 비용 =  [(i~k)의 합 + (k+1~j)의 합] + 두 그룹을 합치는 비용

 

5.  코드 작성

▶ Java 11 ( 36468KB, 440ms)

import java.io.*;
import java.util.*;

public class Main {
    static int T,K;
    static int[] fileSize, cumSum;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        T = Integer.parseInt(br.readLine());
        while(T-->0) {
            K = Integer.parseInt(br.readLine());
            fileSize = new int[K+1];
            cumSum = new int[K+1];
            // dp[i][j] : i~j 페이지 합의 최솟값
            dp = new int[K+1][K+1];

            // cumSum에 차례대로 누적합 저장 bc) 연속한 합을 바로 구하기 위함
            // ex) a, a+b, a+b+c, a+b+c+d, ...
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int k = 1; k <= K; k++) {
                fileSize[k] = Integer.parseInt(st.nextToken());
                cumSum[k] = cumSum[k-1] + fileSize[k];
            }

            // 4개의 장을 합치기 위해서는 한장,두장,세장 각각을 합치는 방법을 알아야한다 -> 해당 부분이 중복이므로 메모제이션 가능
            for (int n = 1; n <= K; n++) {
                for (int from = 1; from + n <= K; from++) {
                    int to = from + n;
                    dp[from][to] = Integer.MAX_VALUE;
                    for (int divide = from; divide < to; divide++) {
                        // 점화식 : dp[i][j] = min(dp[i][k] + dp[k + 1][j] + i~j까지의 비용
                        dp[from][to] = Math.min(dp[from][to], dp[from][divide] + dp[divide+1][to] + cumSum[to] - cumSum[from - 1]);
                    }
                }
            }
            bw.write(dp[1][K]+"\n");
        }
        bw.flush();
    }
}

 

6.  결과