Gold III 난이도 문제를 C++로 풀이한 내용입니다. 여러 개의 파일과 각 파일의 크기를 입력받아, 모든 파일을 하나의 파일로 합치는 데 필요한 최소 비용을 계산하는 문제입니다.

백준 11066: 파일 합치기

문제 소개

문제 번호: 11066
문제명: 파일 합치기
난이도: Gold III
사용 언어: C++
실행 시간: 80 ms
메모리: 3984 KB
문제 요약: 주어진 여러 개의 파일을 순서대로 합치는 데 드는 비용의 총합을 최소화하는 문제입니다. 두 파일을 합칠 때 드는 비용은 두 파일의 크기의 합과 같습니다.

접근 방법

이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 파일들을 합치는 과정은 구간에 대한 최적화 문제로 볼 수 있습니다.

문제의 구조 이해: 파일 $i$ 부터 $j$ 까지 합치는 최소 비용을 구하는 것은, 이 구간을 두 부분으로 나누어 각각의 최소 비용을 더하고, 두 부분을 합치는 비용을 더하는 것으로 표현할 수 있습니다. 즉, $cos t [i] [j] = min (cos t [i] [k] + cos t [k + 1] [j]) + sum (c [i] \dots c [j])$ (단, $i \leq k < j$ ) 형태가 됩니다.
알고리즘/자료구조 선택:
- 동적 계획법 (DP): 작은 구간에 대한 최적의 해를 구해 큰 구간의 최적의 해를 만드는 방식입니다.
- 2차원 배열: cost[i][j]는 파일 $i$ 부터 $j$ 까지 합치는 최소 비용을 저장하고, total_cost[i][j]는 이 구간의 누적 최소 비용을 저장하는 데 사용됩니다.
- 누적 합 배열 (또는 유사한 방식): cost[i][j] 계산 시 i부터 j까지 파일 크기의 합을 효율적으로 구하기 위해 사용합니다. 코드에서는 cost[i][j] 자체가 i부터 j-1까지의 누적합으로 정의됩니다.
방법 선택 이유:
- 이 문제는 최적 부분 구조와 중복되는 부분 문제를 가지고 있습니다. 예를 들어, 파일 1부터 5까지 합치는 최소 비용을 계산할 때, 파일 1부터 3까지 합치는 최소 비용과 파일 4부터 5까지 합치는 최소 비용이 필요합니다. 이 두 하위 문제의 결과는 다른 구간의 합을 계산할 때도 재사용될 수 있습니다.
- DP는 이러한 중복 계산을 피하고 효율적으로 최적의 해를 찾을 수 있는 강력한 기법입니다.

풀이 과정

입력 처리: 테스트 케이스의 개수 T를 읽고, 각 테스트 케이스마다 파일의 개수 n과 각 파일의 크기 c[1]부터 c[n]까지를 입력받습니다.
DP 테이블 초기화:
- cost[i][j]: 파일 i부터 j까지의 파일 크기 합을 저장합니다. 이는 cost[i][j-1] + c[j]로 계산하여 효율적으로 구합니다.
- total_cost[i][j]: 파일 i부터 j까지 합치는 데 드는 최소 총 비용을 저장합니다.
  - total_cost[i][i]는 0으로 초기화합니다 (파일 하나는 합칠 필요가 없으므로 비용 0).
  - 나머지 total_cost[i][j]는 매우 큰 값(예: 1e9)으로 초기화하여 min 연산에서 항상 더 작은 값을 선택하도록 합니다.
DP 계산:
- 구간의 길이 len을 2부터 n까지 증가시킵니다.
- 구간의 시작점 i를 1부터 n - len + 1까지 증가시킵니다.
- 구간의 끝점 j는 i + len - 1로 결정됩니다.
- 이제 구간 [i, j]를 두 개의 하위 구간 [i, k]와 [k+1, j]로 나누는 모든 가능한 분할점 k ( i <= k < j)에 대해 반복합니다.
- 각 분할점 k에 대해, total_cost[i][k] + total_cost[k+1][j] + cost[i][j]를 계산합니다. 이는 두 하위 구간을 합치는 데 드는 최소 비용과, 합쳐진 두 파일을 최종적으로 하나로 만드는 데 드는 비용의 합입니다.
- 계산된 값을 total_cost[i][j]의 현재 값과 비교하여 더 작은 값으로 갱신합니다.
결과 출력: 최종적으로 total_cost[1][n]은 파일 1부터 n까지 모두 합치는 데 드는 최소 비용이 됩니다. 이 값을 출력합니다.

핵심 아이디어: 구간의 길이를 늘려가면서 DP 테이블을 채웁니다. 길이가 len인 구간 [i, j]를 계산할 때는, 이미 계산이 완료된 길이가 len보다 작은 하위 구간들의 최적해를 활용합니다.

주의할 점:

배열 인덱스를 1부터 시작하는 것이 문제의 표기와 일치하여 편리합니다.
total_cost의 초기값을 충분히 큰 값으로 설정해야 min 연산이 올바르게 작동합니다.
cost[i][j]는 i부터 j까지의 파일 크기 합이며, total_cost[i][j]는 i부터 j까지 모든 파일을 합치는 데 드는 최소 비용입니다. 이 둘을 혼동하지 않아야 합니다.

코드 설명

#include <iostream>
#include <algorithm>
using namespace std;

int n, c[501], cost[501][501], total_cost[501][501]; // 1based mat

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        // c 배열에 파일 크기 입력 (1부터 n까지)
        for (int i = 1; i <= n; i++) cin >> c[i];

        // cost[i][j]: i~j 파일 구간의 파일 크기 합
        // total_cost[i][j]: i~j 파일 구간을 합치는 모든 과정의 cost 누적 최솟값
        // total_cost[i][i] = 0: 파일이 하나인 경우 합치는 비용 없음
        // total_cost[i][j] = 1e9: min() 연산을 위한 초기값 (매우 큰 값)
        for (int i = 1; i <= n; i++){
            for (int j = i; j <= n; j++) {
                // cost[i][j]는 cost[i][j-1] + c[j]로 계산하여 효율적으로 파일 크기 합을 구함
                cost[i][j] = cost[i][j-1] + c[j];
                // 대각선 (i == j)은 0, 나머지는 무한대로 초기화
                total_cost[i][j] = (i == j) ? 0 : 1e9;
            }
        }
        
        // len: 합치려는 파일 구간의 길이 (2부터 n까지)
        // len이 2이면 파일 2개를 합치는 경우, len이 n이면 파일 n개를 모두 합치는 경우
        for (int len = 2; len <= n; len++) 
            // i: 파일 구간의 시작점 (1부터 n - len + 1까지)
            // j: 파일 구간의 끝점 (i + len - 1)
            for (int i = 1; i + len - 1 <= n; i++) { 
                int j = i + len - 1; 
                // k: 파일 구간 [i, j]를 두 개의 하위 구간 [i, k]와 [k+1, j]로 나누는 분할점
                // k는 i부터 j-1까지 변화
                for (int k = i; k < j; k++)
                    // total_cost[i][k] + total_cost[k+1][j]: 두 하위 구간을 합치는 데 드는 최소 비용
                    // cost[i][j]: 두 하위 구간으로 합쳐진 파일들을 다시 하나로 합치는 데 드는 비용 (파일 크기 합)
                    // 위 세 값을 더한 것이 현재 분할점 k를 사용했을 때의 총 비용
                    // 이를 기존 total_cost[i][j]와 비교하여 최솟값으로 갱신
                    total_cost[i][j] = min(total_cost[i][j], total_cost[i][k] + total_cost[k+1][j] + cost[i][j]);
            }

        // 최종 결과: 파일 1부터 n까지 모두 합치는 데 드는 최소 비용
        cout << total_cost[1][n] << "\n";
    }
    return 0;
}

복잡도 분석

시간 복잡도:
- 최외곽 루프 len은 n번 반복합니다.
- 중간 루프 i는 n번 반복합니다.
- 내부 루프 k는 n번 반복합니다.
- 따라서 전체 시간 복잡도는 $O (n^{3})$ 입니다.
공간 복잡도:
- c, cost, total_cost 배열은 모두 $O (n^{2})$ 크기를 가집니다.
- 따라서 전체 공간 복잡도는 $O (n^{2})$ 입니다.

배운 점

이 문제를 통해 동적 계획법의 기본 원리와 구간 DP에 대해 다시 한번 숙지할 수 있었습니다. 특히, 문제를 작은 부분 문제로 나누고, 각 부분 문제의 결과를 저장하여 재활용하는 방식이 큰 문제 해결에 얼마나 효율적인지 알 수 있었습니다. 또한, DP 테이블의 초기화와 반복문의 순서 (구간의 길이를 늘려가는 방식)가 올바른 해를 얻는 데 중요함을 배웠습니다. cost[i][j]와 total_cost[i][j]의 역할을 명확히 구분하는 것이 혼동을 줄이는 데 도움이 되었습니다.