[백준] 파일 합치기 (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을 초과하지 않는다.

 

출력

각 테스트 데이터마다 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

 

접근법

DP 문제를 풀려고 백준에서 찾아 들어간거라서 DP로 접근해서 풀었다.

 

처음에는 그리디하게 접근해서 풀 수 있는 문제인가 싶었는데(가장 작은 두 챕터를 먼저 합치는 방식). 당장 예제만 해도 그렇게 접근하면 오답이 나왔다. 반드시 주어진 챕터 순서대로 합쳐야 한다는 조건이 존재하기 때문에 그리디 알고리즘으로 풀 수 없다.

 

그래서 DP로 접근을 시도했다. 처음에는 O(N)에 풀수 있는 문제인가 싶어서, 챕터를 순서대로 탐색해 나가면서, 각 챕터에서

1. 현재 챕터와 바로 이전의 챕터를 합친 다음 (= X1), 챕터 1부터 현재 챕터의 전 전 챕터까지 합친 임시파일 X2와 X1을 합치는 경우
2. 챕터 1부터 바로 이전의 챕터까지 합친 임시파일 X1과 현재 챕터를 합친 경우

두 경우의 비용을 비교해서 더 적은 비용을 dp 배열에 저장해 나가는 식으로 풀었더니 바로 틀려버렸다.

 

아마도 임시 파일을 만들 때 2개가 아니라 n개 까지 합칠 수 있기 때문에, 그 경우를 고려하지 않아서 틀린 것으로 보인다. 정확한 이유는 모르겠지만 아무튼 틀렸다.

 

그래서 구글링을 통해 챕터를 순서대로 합치는 모든 경우를 전부 확인하되, dp를 활용해서 연산을 줄이는 방식을 알아내서 그렇게 풀었다.

 

핵심이 되는 접근 방식은 다음과 같다.

챕터 1(C1)부터 챕터 n(Cn)까지 합치는 모든 경우는 다음과 같다.

Cx부터 Cy를 합친 임시파일을 Tx/y라고 할 때,(1 <= x < y <= n),
C1과 T2/n을 합치는 경우,
T1/2와 T3/n을 합치는 경우,
...
T1/n-2와 Tn-1/n을 합치는 경우,
T1/n-1과 Cn을 합치는 경우.

챕터를 반드시 순서대로 합쳐야 하기 때문에 위의 경우 말고는 존재하지 않는다는 것을 알 수 있다.

위의 경우들의 합치는 비용들의 최솟값을 전부 구한 뒤 그 중 다시 최솟값을 구하면 그게 정답이다.

 

하지만 여기서 문제가 있다.

Tx/y를 만드는 데 필요한 최소 비용을 알아야하는데, 이걸 구하려면 다시

Cx와 Tx+1/y를 합치는 경우,
Tx/x+1과 Tx+2/y를 합치는 경우,
...

이 경우의 비용들을 전부 구해서 또 최소비용을 찾아야 하기 때문이다.

 

여기서 이 문제가 Divide and Conquer로 접근해서 DP를 활용하여 풀 수 있는 문제임을 알 수 있다.

 

챕터 x부터 챕터 y까지 합치는데 필요한 최소 비용을 minCost[x][y]라고 하자. 즉 이 값은 Tx/y를 만드는 데 필요한 최소 비용이다.

(단 1 <= x <= y <= n. 챕터 순서대로 합쳐야 하므로 x > y 인 경우는 고려하지 않는다)

 

우리가 알고 있는 값으로 이 minCost 배열을 초기화 할  수 있다.

먼저 minCost[x][x] (Tx/x)의 경우에는 그냥 Cx를 만드는 데 필요한 비용이므로, 0이다.

 

minCost[x][x] = 0

 

그리고 minCost[x][x + 1]은 Cx와 Cx+1을 합치는 1가지의 경우밖에 없으므로

 

minCost[x][x + 1] = (Cx의 크기) + (Cx+1의 크기)

 

이제 minCost[x][x + 2]의 경우를 고려해보자. 챕터 3개를 합치는 경우이다. 이 때는

Cx와 Tx+1/x+2를 합쳐서 Tx/x+2를 만드는 데 드는 최소 비용
Tx/x+1과 Cx+2를 합쳐서 Tx/x+2를 만드는 데 드는 최소 비용

이 두 값을 비교해서 더 작은 값을 선택하면 된다.

 

그런데 여기서 Tx+1/x+2과 Tx/x+1를 만드는 데 필요한 최소 비용은 우리가 앞에서 초기화 해둔 minCost[x][x + 1]을 사용하면 된다는 것을 알 수 있다.

 

그러면 Cx와 Tx+1/x+2를 합치는 비용(또는 Tx/x+1과 Cx+2를 합치는 비용)은 어떻게 구할까?

답을 먼저 말하자면 Cx + Cx+1 + Cx+2 이다.

왜냐하면 Cx의 크기와, Tx+1/x+2의 크기의 합인데, Cx의 크기는 Cx이고, Tx+1/x+2의 크기는 Cx+1 + Cx+2이기 때문이다.

 

이 때 Cx + Cx+1 + Cx+2를 조금 더 간단하게 구하기 위해서 누적합을 이용한다.

챕터 1부터 챕터 x까지의 누적합을 sum[x]라고 할 때,

Cx + Cx+1 + Cx+2 = sum[x+2] - sum[x - 1] 이다.

 

따라서

Cx와 Tx+1/x+2를 합쳐서 Tx/x+2를 만드는 데 드는 최소 비용
= minCost[x][x] + minCost[x + 1][x + 2] + sum[x + 2] - sum[x - 1]
Tx/x+1과 Cx+2를 합쳐서 Tx/x+2를 만드는 데 드는 최소 비용
=minCost[x][x + 1] + minCost[x + 2][x + 2] + sum[x + 2] - sum [x - 1]

이다.

 

minCost[x][x + 2]는 이 두 값 중 더 작은 값이 된다.

 

여기까지의 내용을 이제 다시 일반화를 하면,

minCost[x][x + k]는 다음과 같다.

minCost[x][x + k] = 
minCost[x][x] + minCost[x + 1][x + k] + sum[x + k] - sum[x - 1],
minCost[x][x + 1] + minCost[x + 2][x + k] + sum[x + k] - sum[x - 1],
...
minCost[x][x + k - 1] + minCost[x + k][x + k] + sum[x + k] - sum[x - 1]
중의 최솟값

 

위 식을 살펴보면 k + 1개의 챕터를 합치는데 필요한 최소 비용인 minCost[x][x + k]를 구하기 위해서는,

k개의 챕터를 합치는데 필요한 비용 (minCost[x + 1][x + k]과 minCost[x][x + k - 1]), k - 1개의 챕터를 합치는 데 필요한 비용 (minCost[x + 2][x + k]과 minCost[x][x + k - 2]), ... , 1개의 챕터를 합치는 데 필요한 비용(minCost[x][x], minCost[x + k][x + k])이 필요하다는 것을 알 수 있다.

 

즉 여기서 얻을 수 있는 결론은

합치는 챕터의 개수를 3, 4, ..., n개까지 순서대로 늘려가면서 값을 채워나가면, dp를 이용해 최솟값을 구할 수 있다는 것이다.

 

이제 코드를 보면 더 확실히 이해가 될 것이다.

 

 

시간 복잡도

O(N^3) 보다는 작다. 

 

 

공간 복잡도

dp 배열에 필요한 K * K * int

 

 

풀면서 놓쳤던 점

모든 경우를 다 따지지 않았음

 

 

이 문제에서 얻어갈 점

DP의 활용

 

 

코드

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

public class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException
    {
        int numOfTestcases = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int testcase = 0; testcase < numOfTestcases; testcase++)
        {
            int numOfChapters = Integer.parseInt(br.readLine());

            int[] chapters = new int[numOfChapters + 1];
            readChapters(chapters);

            sb.append(getMinMergingCost(chapters)).append('\n');
        }

        System.out.println(sb.toString());
    }

    static int getMinMergingCost(int[] chapters)
    {
        //DP에 이용할 배열. minCost[x][y]는 챕터 x부터 챕터 y를 합치는데 드는 최소 비용.
        int[][] minCost = new int[chapters.length][chapters.length];
        initMinCost(minCost, chapters); //초깃값을 넣어준다.

        //연산을 빠르게 하기 위한 누적합 배열.
        int[] chapterSumTo = new int[chapters.length];
        initChapterSumTo(chapterSumTo, chapters);

        //모든 챕터를 전부 합치는 경우를 구하기 위해서, 챕터를 합치는 범위를 챕터 2개, 3개씩 늘려간다
        for (int range = 2; range < chapters.length; range++)
        {
            for (int startIdx = 1; startIdx + range < chapters.length; startIdx++)
            {
                int endIdx = startIdx + range;
                for (int midIdx = startIdx; midIdx < endIdx; midIdx++)
                {
                    minCost[startIdx][endIdx] = Math.min(
                            minCost[startIdx][endIdx],
                            minCost[startIdx][midIdx] + minCost[midIdx + 1][endIdx] + chapterSumTo[endIdx] - chapterSumTo[startIdx - 1]
                    );
                }
            }
        }

        return minCost[1][chapters.length - 1];
    }

    static void initChapterSumTo(int[] chapterSumTo, int[] chapters)
    {
        //startIdx = 1인 경우를 위해서 chapterSumTo[0]을 0으로 초기화.
        chapterSumTo[0] = 0;
        chapterSumTo[1] = chapters[1];
        for (int i = 2; i < chapters.length; i++)
            chapterSumTo[i] = chapterSumTo[i - 1] + chapters[i];
    }

    static void initMinCost(int[][] minCost, int[] chapters)
    {
        //최솟값을 갱신해가며 저장하는 배열이기 때문에, 먼저 Integer.MAX_VALUE 로 초기화해준다. 
        for (int[] row : minCost)
            Arrays.fill(row, Integer.MAX_VALUE);

        for (int i = 1; i < minCost.length - 1; i++)
        {
            minCost[i][i] = 0; //이미 존재하는 챕터는 합치는 비용이 0
            minCost[i][i + 1] = chapters[i] + chapters[i + 1]; //연속된 두 챕터를 합치는 최소 비용은 두 챕터의 크기의 합
        }

        minCost[minCost.length - 1][minCost.length - 1] = 0;
    }

    static void readChapters(int[] chapters) throws IOException
    {
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < chapters.length; i++)
            chapters[i] = Integer.parseInt(st.nextToken());
    }
}