[BOJ 11066] 파일 합치기

https://www.acmicpc.net/problem/11066

문제를 대충 읽어서 바로 옆에있는 파일들만 합칠 수 있다는 것을 못보고 우선순위큐로 풀었다가 예제 2번이 이상하게 나와서 다시 꼼꼼하게 읽어보았다..

1. 접근

예제 1번을 먼저 보자.

0	1	2	3
40	30	30	50
70	80
150

$70 + 80 + 150 = 300$

[40, 30, 30, 50] 을 두 그룹으로 나눈 뒤, 더한 값이 최소가 되어야 한다.

[{40, 30, 30}, 50] 으로 나눈다면, [{40, 30}, 50] or [40, {30, 50}] 두가지의 방법으로 다시 앞의 그룹을 나눌 수 있다.

전체 비용이 최소가 되기 위해선 소 그룹인 {40, 30, 30} 에서 사용된 비용도 최소가 되어야 한다.

---

2. 풀이

dp[i][j] = '인덱스 i에서 j 범위의 파일들을 합쳤을 때 발생하는 최소 비용'

이렇게 설정을 하면, 풀이가 간단해진다.

i = 0, j = 3으로 예시를 들어보자.

dp[0][3] = '인덱스 0부터 3까지의 파일들을 합쳤을 때 발생하는 최소 비용' 이다.

접근에서 말한 것과 같이 그룹을 나눈 뒤, 나뉘어진 각 그룹들의 최솟값을 더해야 전체 그룹의 최소가 될 것이다.

따라서 0부터 3까지를 그룹을 나눠보면, [0, {1,2,3}], [{0, 1}, {2, 3}], [{0, 1, 2}, 3] 으로 나눌 수 있고,

첫번째 그룹을 보면, {1, 2, 3} 에서의 최솟값이 나와야 0과 합쳤을 때도 최소가 된다는 것을 알 수 있다.

따라서 첫번째 그룹을 수식으로 나타낸다면 다음과 같이 나타낼 수 있다.

이 때, 병합 되는 과정 뿐만 아니라 결과도 더해줘야 한다. 이 결과는 직접 더해서 알 수도 있지만, 어차피 범위 내 수의 부분합 이므로 미리 배열을 만들어 구해놓았다.

dp[0][3]을 구하는 전체 그룹을 포함하는 식은 다음과 같이 나타낼 수 있다.

$dp[0][3]=\min (dp[0][0]+dp[1][3],dp[0][1]+dp[2][3],dp[0][2]+dp[3][3])+psum$

여기까지만 생각하고, 무지성 거인처럼 코드 때려박았다가 답이 안나와서 왜 안나오지? 하고 아무 잘못없는 점화식을 건드렸었다.....

문제는 갱신되는 순서였다.

원소가 3개인 그룹이 존재할 때, 이미 그룹 내 작은 그룹들의 최솟값이 구해져 있어야 한다.

그러므로...

범위가 작을수록, 먼저 갱신이 되어야 한다.
그렇지 않으면 잘못된 값이 도출,,,,,,

소스코드 의 for문에 있는 r은 원소의 범위를 의미한다. 범위를 작은 것 부터 큰 것 까지 갱신을 순서대로 해야 큰 범위의 그룹의 최솟값을 계산할 수 있다.

---

3. 소스코드

// https://www.acmicpc.net/problem/11066
// 11066번 파일 합치기

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int INF = 987654321;
int tc, k, dp[501][501], sum[501];

int main() {
    for(scanf("%d", &tc); tc--;) {
        scanf("%d", &k);

        memset(sum, 0, sizeof(sum));
        memset(dp, 0, sizeof(dp));

        for(int s, i = 0; i < k; i++) {
            scanf("%d", &s);
            if(i == 0) {
                sum[i] = s;
                continue;
            }
            sum[i] = sum[i-1] + s;
        }
        
        // range
        for(int r = 1; r < k; r++)
            // start
            for(int s = 0; s + r < k; s++) {
                // end
                int e = s + r;
                int psum = sum[e] - sum[s-1];
                dp[s][e] = INF;
                for(int k = s; k < e; k++)
                    dp[s][e] = min(dp[s][e], dp[s][k] + dp[k+1][e] + psum);
            }
        
        printf("%d\n", dp[0][k-1]);
    }
}