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. 비용은 두 가지로 나눌 수 있다. 하나는 "현재 두 파일을 합치는 데 드는 비용(단순한 용량 합)"이고, 다른 하나는 "이전까지 합치는 과정에서 누적된 최소 비용"이다.

 

 

 

using System.Text;

public class BackJoon
{
    public static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++)
        {
            int K = int.Parse(Console.ReadLine());
            int[] arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
           sb.AppendLine(ChapterSum(K,arr).ToString());
        }
        Console.WriteLine(sb.ToString());
        
        
    }

    public static int ChapterSum(int K , int[] arr)
    {
        // 최솟값을 저장하기 위함 ex :  1, 1 이면 1부터 1까지 / 1, 2 이면 1부터 2까지
        int[,] minArr = new int[K, K];
        
        // 데이터의 누적합을 저장
        int[] arrSum = new int[K];

        arrSum[0] = arr[0];
        for (int i = 1; i < K; i++)
        {
            arrSum[i] = arrSum[i - 1] + arr[i];
        }

        // // 기본 (자기 자신 저장)
        // for (int i = 0; i < K; i++)
        // {
        //     minArr[i,i] = arr[i];
        // }
        
        // 길이 1은 이미 했으니, 2부터 모든 구간을 다 포함하는 K까지 
        // 주의 : 길이 2라는 것은 자기 자신을 포함한 것, 따라서 K까지 가도 자기 자신을 포함한 것이라 등호를 써 줘야 한다.
        for (int length = 2; length <= K; length++)
        {
            // 가능한 경우의 수를 모두 체크 
            // 배열 밖을 넘어가면 안되니까  K - Length를 해줌
            for (int i = 0; i <= K - length; i++)
            {
                // 현재 반복에서 범위 ( 끝 숫자 )
                int j = i + length - 1;
                minArr[i, j] = int.MaxValue;

                for (int t = i; t < j; t++)
                {
                    // 현재 값은, t를 기준으로 나눈 양 쪽을 더해준 후, 합치는데 더하는 비용을 합한 것과 같다.
                    int cost = arrSum[j] - (i > 0 ? arrSum[i - 1] : 0);
                    int temp = minArr[i, t] + minArr[t + 1, j] + cost;
                    minArr[i,j] = Math.Min(minArr[i,j],temp);
                }
            }
        }

        return minArr[0, K - 1];
    }
}

 

아이디어는 다음과 같다.

1. 결국 두 덩이를 합쳐야 한다. 이 때 합쳐질 때 더해지는 값 ( 데이터의 총 량)은 쉽게 구할 수 있다. ( 누적합을 이용)

2. 두 덩이가 항상 최솟값을 유지하게 해야 한다. ( 따라서, 총 데이터 길이를 가능한 부분들로 구분하고 더해보면서 최솟값을 찾음 ) 

 

중간에 실수한 부분은, 자기 자신을 합칠 때에는 0을 넣어 주어야 하는데 자신의 데이터량을 더해주었다.

나중에 누적합을 이용해 데이터의 총량은 따로 더해주기에, 0을 넣어 주는 것이 맞다.

 

이 문제는 전형적인 구간 DP 문제이다.
처음에는 구간 길이(length)를 2부터 K까지 확장하면서 푸는 방식을 떠올리지 못했다.
또한 2차원 배열을 사용해야 한다는 점도 늦게 깨달았다. (파일을 구간 단위로 합치는 비용을 저장해야 하므로 시작점과 끝점을 모두 관리하는 구조가 필요했다.)
앞으로 난이도가 있는 DP 문제를 풀 때는, "구간 단위 문제 → 2차원 배열 사용"을 우선적으로 고려해야겠다.