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 이다.
소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.
입력
예제 입력 복사 2
4
40 30 30 50
15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32
예제 출력 복사 300
864
1. 접근
예시 테스트 케이스 중 첫 번째 경우에 대해 생각해보자.
{40, 30, 30, 50} 을 우선 두 그룹으로 나눠야 한다. 나눠지는 경우의 수는 여러가지일 것이다.
{40} / {30, 30, 50} 으로 나눈 경우에, 뒷 그룹 또한 더 나눠지는 방법이 존재한다.
따라서 단순히 테스트 케이스를 계속 두 그룹으로 나누는, 즉 이진 트리를 만드는 모든 방법에 대해 최소 비용을 계산해야 한다.
하지만 같은 데이터를 중복해서 연산하는 과정이 겹치기 때문에, 메모이제이션을 통한 다이나믹 프로그래밍 기법을 통해 접근해야 한다.
2-1) 풀이 1.
novel[i] = 소설의 i번째 장의 크기라 하고,
다이나믹 프로그래밍 기법을 통해, 점화식을 세우기 위한 배열 dp[i][j]를 정의해보자.
dp [ i ][ j ] = i번째 장부터 j번째 장까지 합치는데 드는 최소한의 비용.
따라서 dp [ i ][ i ] = novel[i], dp[i][i+1] = novel[i]+novel[i+1] 임을 쉽게 알 수 있다.
또한 dp [ i ][ j ] 를 두 그룹으로 나누는 기준이 되는 k에 대해(i<=k<j) 다음 점화식을 생각할 수 있다.
dp [ i ][ j ] = min(i <= k < j) { dp [ i ][ k ] + dp [ k+1 ][ j ]} + psum [ i ][ j ] ( psum [ i ][ j ] 는 novel [ i ][ j ] 의 i부터 j까지의 부분합)
결국 삼중 포문을 돌면서 dp [ ][ ] 를 갱신해가면서, 최종적으로 dp [ 1 ][ N ] 을 출력하면 되는 문제였다. O(N^3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include < stdio.h>
#include < string .h>
#include < limits.h>
#include < algorithm>
using namespace std ;
int dp[501 ][501 ];
int cost[501 ];
int sum[501 ];
int t, k, i;
int main() {
scanf ("%d" , & t);
while (t- - ) {
scanf ("%d" , & k);
for (i = 1 ; i < = k; + + i) {
scanf ("%d" , & cost[i]);
sum[i] = sum[i - 1 ] + cost[i];
}
for (int d = 1 ; d < k; + + d) {
for (int tx = 1 ; tx + d < = k; + + tx) {
int ty = tx + d;
dp[tx][ty] = INT_MAX;
for (int mid = tx; mid < ty; + + mid)
dp[tx][ty] =
min(dp[tx][ty], dp[tx][mid] + dp[mid + 1 ][ty] + sum[ty] - sum[tx - 1 ]);
}
}
printf ("%d\n" , dp[1 ][k]);
}
return 0 ;
}
cs
2-2) 풀이 2.
예를 들어, 6개의 파일에 대해 dp[1][6]을 채우는 방법은, 어느 기점을 기준으로 왼쪽 최소비용, 오른쪽 최소비용의 합이다.
그 중 왼쪽은 다시 어느 기점을 기준으로 왼쪽 최소비용, 오른쪽 최소비용의 합으로 이루어져 있을 것이다.
이렇게 계속 재귀적으로 나누어가다 보면 더이상 쪼개지지 않는 경우에 도달하고, (파일이 한개라면 비용은 0이다)
이 비용을 리턴받아 왼쪽, 오른쪽 최소비용을 채워나간다.
코드로 옮기자면 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include < stdio.h>
#include < string .h>
#include < algorithm>
using namespace std ;
int dp[501 ][501 ];
int cost[501 ];
int sum[501 ];
int t, k, i;
int dpf(int tx, int ty) {
if (dp[tx][ty] ! = 0x3f3f3f3f )
return dp[tx][ty];
if (tx = = ty)
return dp[tx][ty] = 0 ;
if (tx + 1 = = ty)
return dp[tx][ty] = cost[tx] + cost[ty];
for (int mid = tx; mid < ty; + + mid) {
int left = dpf(tx, mid);
int right = dpf(mid + 1 , ty);
dp[tx][ty] = min(dp[tx][ty], left + right);
}
return dp[tx][ty] + = sum[ty] - sum[tx - 1 ];
}
int main() {
scanf ("%d" , & t);
while (t- - ) {
memset(dp, 0x3f , sizeof (dp));
scanf ("%d" , & k);
for (i = 1 ; i < = k; + + i) {
scanf ("%d" , & cost[i]);
sum[i] = sum[i - 1 ] + cost[i];
}
printf ("%d\n" , dpf(1 , k));
}
return 0 ;
}
cs
그럼 세 파일에 대해 합치는 비용의 경우 중 한 가지, {{1+2}+{3}} 은 왼쪽을 합치는 비용(3) 과 오른쪽을 합치는 비용(0)에
전체 구간의 파일 크기의 합과 같다.
이 작은 케이스를 가장 큰 케이스에 투영 시키는 것이다.
2-2) 풀이 3.
풀이 1 대로면 대략 125,000,000 번의 연산으로 140ms 정도로 AC를 받는다.
풀이 2 대로면 대략 125,000,000 번의 연산으로 580ms 정도로 AC를 받는다. (함수호출등의 이유로 더 오래 걸린 것이다)
하지만 맞은 사람들의 코드들을 보면 대부분 20ms 내외로 AC를 받았는데, 감명깊어 여기에 풀이를 옮긴다.
기본 아이디어는 같으나 결과적으론 최적화의 문제인데,
다이나믹 프로그래밍 문제 중에 다음과 같은 특별한 점화식에 대해서 최적화가 가능하다고 한다.
이를 Kruth's optimization 이라 부른다.
1) 사각부등식
C [ a ][ c ]+C[b][d]<=C[a][d]+C[b][c] (a<=b<=c<=d)
2) 단조증가
C [ b ][ c ]<=C[a][d] (a<=b<=c<=d)
위 두 조건을 만족하는 C [ ][ ] 에 대해,
점화식이 dp [ i ][ j ] = min(i < k < j) { dp [ i ][ k ] + dp [ k ][ j ]} + C [ i ][ j ] 꼴이라 하자.
이 때, num [ i ][ j ] 란 dp [ i ][ j ] 가 최소가 되게 하는 k(i < k < j) 값을 저장하는 배열이라 정의하면, 다음이 성립한다.
num[ i ][ j-1 ] <= num[i][j] <= num [ i+1 ][ j ]
풀이 1에선 i부터 j까지의 모든 k에 대해 최소값을 구하느라 O(N^3)이 걸렸지만,
실제로는 정답인 k가 저 좁은 범위안에 있기 때문에 모든 k를 살펴볼 필요가 없으므로 최적화가 O(N^2)로 가능하다는 이론이다.
증명은 다음페이지를 참조하자.
http://www.egr.unlv.edu/~bein/pubs/knuthyaotalg.pdf
실제로 최적화가 적용가능한지 살펴보기 위해, 먼저 우리의 psum [ ][ ] 배열이 C [ ][ ] 꼴 인지 생각해보자.
1) 사각부등식에 대해, 앞의 항과 뒤의 항 모두 b~c의 novel [ ][ ] 를 중복해서 더하므로, 등호를 만족한다.
2) 단조증가에 대해, psum [ b ][ c ]<=psum[a][d] 임은 자명하다.
다음으로 점화식에 대해 생각해보면, 우리의 점화식은 다음과 같았다.
i<=k<j인 k에 대해,
dp [ i ][ j ] = min(i <= k < j) { dp [ i ][ k ] + dp [ k+1 ][ j ]} + psum [ i ][ j ] -> i부터 j까지의 최소합비용
이제 Kruth's optimization을 적용하기 위해, 점화식을 수정해주자.
i<k<j인 k에 대해,
dp2 [ i ][ j ] = min(i < k < j) { dp2 [ i ][ k ] + dp2 [ k ][ j ]} + psum [ i ][ j ] -> i + 1부터 j까지의 최소합비용
점화식이 조금 수정되었지만, dp [ i ][ j ] = dp2[i-1][j] 이기 때문에 여전히 같은 기능을 수행한다.
정답은 dp2 [ 0 ][ N ] 을 출력하면 된다.
d=2 부터, i=0 부터 시작하는 것을 주의하라.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
for (scanf ("%d" , & T); T- - ;) {
scanf ("%d" , & N);
for (int i = 1 ; i < = N; i+ + )
scanf ("%d" , & novel[i]), psum[i] = psum[i - 1 ] + novel[i];
for (int i = 1 ; i < = N; i+ + )
num[i - 1 ][i] = i;
for (int d = 2 ; d < = N; d+ + ) {
for (int i = 0 ; i + d < = N; i+ + ) {
int j = i + d;
dp2[i][j] = 2e9 ;
for (int k = num[i][j - 1 ]; k < = num[i + 1 ][j]; k+ + ) {
int v = dp2[i][k] + dp2[k][j] + psum[j] - psum[i];
if (dp2[i][j] > v)
dp2[i][j] = v, num[i][j] = k;
}
}
}
printf ("%d\n" , dp2[0 ][N]);
}
return 0 ;
}
cs
3. 후기
dp들을 갱신해가는 과정은 연쇄행렬 최소곱 알고리즘 의 과정과 닮아있다.