[C++] 백준 11066번: 파일 합치기 (DP)

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

소설의 각 장들의 파일의 크기가 주어졌을 때, 이 파일들을 하나로 합칠 때 필요한 최소비용을 구하여라.

---

시간복잡도 어림하기

브루트포스 알고리즘

 파일을 합칠 때에는 인접한 두 파일(임시 파일 포함)을 합쳐야 합니다. 이를 작은 파일을 합쳐나가며 모든 파일을 합치는 과정의 반대로 생각하면, 큰 파일 하나를 계속 두 파일로 나누는 것과 같습니다. 즉, 주어진 파일들로 이진트리를 만드는 것입니다.

 n개의 노드로 이진트리를 구성하는 경우의 수는 (2n)! / n!(n + 1)! 이라고 합니다. 문제에서 n의 최댓값은 500이므로 제한 시간 내에 해결할 수 없는 수치임을 알 수 있습니다.

 * 이진트리를 만드는 경우의 수는 저도 검색을 통해 알게 되었습니다. 이처럼 정확하게 경우의 수를 구할 수 없는 문제는 대략적인 감으로 추정하는 것이 좋을 것 같습니다. 아니면 일단 시도해보고 결과를 확인해보는 것도 좋은 방법이겠네요!

 

DP 알고리즘

 파일을 합치는 것은 최소 비용으로 이진트리를 만드는 것임을 알 수 있었습니다. 이때, 같은 데이터를 중복하여 연산하는 경우가 자주 나타날 수 있습니다. 따라서 메모이제이션을 통해 중복된 연산을 제거하여 메모이제이션을 추가한 완전탐색 DP 알고리즘으로 문제를 해결해 봅시다.

---

알고리즘 설계하기

 위에서 간단히 알아봤지만, 구체적으로 최소 비용을 어떻게 구하는지 알아봅시다.

파일 크기가 40, 30, 30, 50인 파일이 있다고 해봅시다.
위에서 알아본 대로 두 개씩 분할 한다면

{40} | {30, 30, 50}
{40, 30} | {30, 50}
{40, 30, 30} | {50} 의 세 가지로 분할 할 수 있습니다. 각 경우의 비용을 계산해보면,
첫 번째 케이스는 {30, 30, 50}을 하나의 파일로 합치는 비용 + (40 + {30 + 30 + 50})
두 번째 케이스는 {40, 30}을 하나의 파일로 합치는 비용 + {30, 50}을 하나의 파일로 합치는 비용 + ({40 + 30} + {30 + 50})
세 번째 케이스는 {40, 30, 30}을 하나의 파일로 합치는 비용 + ({40 + 30 + 30} + 50)으로 계산됩니다.

이때, 마지막에 더해지는 수를 잘 보시면 세 케이스 모두 40 + 30 + 30 + 50으로 모든 범위의 수를 더하는 것과 같습니다.

즉, st에서 ed 사이에 있는 i에 대해 i번째를 기준으로 파일을 분할한다고 하면 그 비용은
{st ~ i}를 하나의 파일로 합치는 비용 + {i + 1 ~ ed}를 하나의 파일로 합치는 비용 + (st ~ ed) 까지의 합으로 계산됩니다.

 

 이를 바탕으로 코드를 설계해봅시다.

int solve(int st, int ed){
    if(st와 ed가 같을 때) return st 파일 비용;
    if(st와 ed가 인접할 때) return st 파일 비용 + ed 파일 비용;
    
    /*메모이제이션 체크 로직*/
    
    /*두 영역으로 분할*/
    for(int mid = st; mid < ed; mid++){
        left = 왼쪽 영역 비용
        right = 오른쪽 영역 비용
    }
    최종 비용 = left + right + st에서 ed까지의 합
}

 이와 같은 완전탐색류 로직에는 기저 조건가 중요합니다. 기저 조건이란 탐색을 마치는 조건을 의미합니다. 위 코드에서 유추할 수 있듯이 이 로직의 기저 조건을 두 가지 입니다.

 

 st와 ed가 같은 경우, 합칠 파일이 하나라는 의미이므로 최소 비용은 해당 파일의 비용과 동일합니다. st와 ed가 인접한 경우, 두 파일의 비용의 합이 최소값이므로 이를 반환합니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#define INF 1e9
using namespace std;

int t, n, a[504], sum[504], dp[504][504];
int solve(int st, int ed){
    if(st == ed) return 0; //한 장을 합치는 데 필요한 최소 비용
    if(st + 1 == ed) return a[st] + a[ed]; //인접 두 장을 합치는 데 필요한 최소비용

    int& ret = dp[st][ed];
    if(ret != INF) return ret; //이미 계산된 경우

    /*mid를 기준, 두 개의 자식으로 분할*/
    for(int mid = st; mid < ed; mid++){
        int left = solve(st, mid); //왼쪽 자식의 최소 비용
        int right = solve(mid + 1, ed); //오른쪽 자식 최소 비용
        ret = min(ret, left + right); //최솟 값 갱신
    }
    return ret += sum[ed] - sum[st - 1]; //누적합 추가
}

int main() {
    cin >> t;
    while(t--){
        /*dp 배열 초기화*/
        fill(&dp[0][0], &dp[0][0] + 504 * 504, INF);
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            sum[i] = sum[i - 1] + a[i]; //누적합 계산
        }
        cout << solve(1, n) << '\n';
    }
    return 0;
}

 테스트케이스 문제이므로 매 테스트케이스마다 사용할 정보를 초기화해주어야 합니다. 위 코드에서는 dp 배열만 초기화합니다. 각 파일의 비용을 저장할 a 배열과 누적합을 구하는 sum배열을 초기화하지 않은 이유는 값이 사용하는 범위는 n으로 제한되어 있고, 해당 값이 매번 입력을 받으면서 갱신되기 때문입니다. 따라서 두 배열을 초기화하지 않아도 문제없습니다.

 

 핵심 로직인 solve 함수는 설계 단계에서 본 것과 동일합니다. 이때, st에서 ed까지의 합을 구할 때, 누적합을 사용하여 구했습니다. 누적합을 사용하지 않으면 매번 O(n)의 탐색을 진행하므로 시간초과가 발생할 수 있습니다. 따라서 누적합을 통해 O(1) 만에 구간합을 구합니다.

---