[11066] 파일 합치기

분류 : 다이나믹 프로그래밍
시간복잡도 : O(K^2)

 

 

다이나믹 프로그래밍의 해결 과정은 다음과 같다.

1. DP를 정의한다.
2. 정의한 DP에 대해 점화식을 세운다.
3. DP를 계산해야 하는 순서에 대해 생각한다.
4. 시간 복잡도를 검증하고 구현한다.

위 문제로 해당 풀이법을 적용해보자.

 

 

1. DP를 정의한다.

이 문제에서의 DP는 다음과 같다.

DP[i][j] = (i 번째 파일부터 j 번째 파일까지를 하나로 합치는데 드는 최소 비용)

 

2. 점화식 세우기

시간복잡도를 계산해보자.

먼저, 첫 함수 호출에서 검사해야하는 값은 {(1, 1) + (2, K)}, {(1, 2) + (3, K)}, ... , {(1, K - 1), (K, K)} 로 1 ~ K - 1의 범위를 확인해야하므로 K - 1개를 확인해야한다. 두 번째 함수에서 구간이 지정되고, 메모이제이션으로 해당 값에 대한 연산이 수행되지 않더라도 총 K - 1 번 확인한다. 초기에는 DP에 저장된 값이 없으므로 많은 재귀 함수의 호출이 이뤄지겠지만, 두 번째 부터는 재귀로 호출되는 횟수가 현저히 적다고 할 수 있다. 따라서 (K - 1) * (K - 1) * C (C는 상수) 이므로 시간복잡도는 O(K^2)이다.

 

DP[2][7]에서 수행되는 연산은 다음과 같다.

(2번째 파일 + 3 ~ 7번째 파일), (2 ~ 3번째 파일 + 4 ~ 7번째 파일), ... , (2 ~ 6번째 파일 + 7번째 파일)

최소 구간이 정해졌다고 가정하고 구한 DP[2][7]은 dp[2][3] + d[4][7] + "두 구간을 합칠 때 드는 비용" 이다.

 

3. 계산 순서

구간의 길이가 1인 경우 합치는 비용은 0일 것이다. 점화식을 통한 계산은 구간의 길이가 작은 DP에서 큰 DP로 수행되어야한다.

 

4. 구현하기

#define INF 1987654321

int T, K, arr[501], dp[501][501];

int getFileCost(int s, int e) {
    if (s == e) return 0;
    if (dp[s][e]) return dp[s][e];

    dp[s][e] = INF;

    for (int i = s; i < e; ++i) {
        dp[s][e] = min(dp[s][e], getFileCost(s, i) + getFileCost(i + 1, e));
    }
    for (int i = s; i <= e; ++i) {
        dp[s][e] += arr[i];
    }

    return dp[s][e];
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> T;

    while (T--) {
        cin >> K;

        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= K; ++i) {
            cin >> arr[i];
        }
        cout << getFileCost(1, K) << "\n";
    }

    return 0;
}