[C++]백준 - 11066번 문제

11066번: 파일 합치기 (acmicpc.net)

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을 초과하지 않는다.

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

동적 프로그래밍을 이용한 문제입니다.

 

예를 들어 입력값이 다음과 같을 때,

 

{40 30 30 50}

 

우리가 구할 최종 목표는 0 ~ 3번째의 파일들을 모두 합친 최소값을 구하는 것입니다.

 

이것을 구하는 함수를 solution(0, 3)이라고 칭하겠습니다.

 

0 ~ 3번째의 최솟값을 구하려면 문제의 조건과 같이 인접한 파일들을 합쳐주어야 하는데, 합치는 방법이 한개가 아닙니다.

 

 

심지어 합치는 방법에 따라서 결과도 다릅니다.

 

여기서 우리는 solution(0, 3)을 구하기 위해 Left ~ Right의 범위를 둘로 나누어 합산하는 과정을 거치겠습니다.

 

solution(0, 3) = min(solution(0, 0) + solution(1, 3) +  {0 ~ 3 까지의 file들의 합},

                          solution(0, 1) + solution(2, 3) + {0 ~ 3 까지의 file들의 합},

                          solution(0, 2) + solution(3, 3) + {0 ~ 3 까지의 file들의 합})

 

Left와 Right의 범위를 반복문을 통해서 쪼개어 주고, 값들 중 가장 작은 값을 결과 값으로 가집니다.

결국, 위와 같이 문제를 쪼개서 solution의 결과를 메모이제이션 하면, 원하던 값을 구할 수 있습니다.

 

코드

---

#include <iostream>
using namespace std;

int K;
int *file;
int *sum_file;      //파일들을 더한 값을 저장하는 배열
int **dp;

//재귀 함수, left에서 right까지의 범위의 최소비용을 구함
int solution(int left, int right)
{
    if(left == right) return 0;
    if(dp[left][right] != 0) return dp[left][right];
    
    int min = 2147483647;	//int의 Max값
    for(int i = left; i < right; i++)
    {
        //left ~ i 까지의 비용 + i+1 ~ right까지의 비용 + left ~ right까지의 크기 합
        int result = solution(left, i) + solution(i + 1, right) 
                    + sum_file[right] - sum_file[left] + file[left];
        if(result < min) min = result;
    }
    dp[left][right] = min;
    return min;
}

int main() 
{
    int T;
    scanf("%d", &T);
    for(int c = 0; c < T; c++)
    {
        scanf("%d", &K);
        file = new int[K];
        sum_file = new int[K];
        dp = new int*[K];
        
        //입력부
        int prev = 0;
        for(int i = 0; i < K; i++)
        {
            scanf("%d", &file[i]);
            dp[i] = new int[K];
            fill_n(dp[i], K, 0);

            sum_file[i] = prev + file[i];
            prev = sum_file[i];
        }
        
        printf("%d\n", solution(0, K-1));
        
        for(int i = 0; i < K; i++) delete[] dp[i];
        delete[] dp;
        delete[] sum_file; 
        delete[] file;
    }
	return 0;
}

 

그 외

---