11066번 : 파일 합치기

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

11066번: 파일 합치기

 

 

이번 문제는, DP 점화식을 생각하지 못해서 구글링 통해서 코드를 참고했다.

 

 

 

---

 

 

뭔가, 사칙 연산에 관련된 것은 항상 같은 방식으로 해결되는 것 같다.

 

 

 

주어진 조건에서, 연속적인 파일들만 합친다고 했으니 덧셈 연산과 동일하다고 생각하면 된다.

 

 

 

덧셈은 사실 결합 법칙이 성립해서, 어떤 순서로 더해도 값은 같다.

 

 

 

이 문제에서는 특별한 조건이 있다. 파일을 만들 때마다, 비용이라는 것을 지불해야 한다.

 

 

 

따라서, 덧셈의 순서에 따라서 계산되는 비용들이 달라지므로 최소값이 발생할 수 있다.

 

 

 

---

 

 

 

DP를 어떻게 정의해야 할까?

 

 

 

문제를 읽다가 보면 비용이라는 개념때문에, 덧셈의 순서에 따라서 값이 달라진다.

 

 

DP를 0부터 K까지 파일 합치기 최소 비용으로 가정해보자.

 

 

 

예제를 살펴보자.

 

 

 

[40 30 30 50] = 40, 30, 30, 50의 파일 합치기 최소 비용

[40] + [30 30 50]

[40 30] + [30 50]

[40 30 30] + [50]

 

 

 

[40 30 30 50]은 위에 세 가지 경우로 모두 커버될 수 있다.

 

 

 

따라서, 이 관계를 바탕으로 점화식을 세워주면 된다.

 

 

 

주의할 점은,

 

 

 

단순히 [40 30 30 50] = [40] + [30 30 50]으로 생각하면 안된다.

 

 

 

왜냐하면, [40]과 [30 30 50]을 합치기 위한 비용도 계산해줘야 한다.

 

 

 

이 부분을 참고해서 코드를 작성하면 된다.

 

 

 

---

 

 

해설코드(C++).

 

 

 

#include <iostream>
#include <algorithm>
 
 
using namespace std;
 
int T, K;
int arr[501];
int dp[501][501];
int sum[501];
 
int solve(int s, int e) {
    if (e - s == 1)
        return arr[s] + arr[e];
    else if (e - s == 0)
        return 0;
 
    if (dp[s][e] != -1)
        return dp[s][e];
 
    for (int i = s; i < e; i++) {
        if (dp[s][e] == -1)
            dp[s][e] = solve(s, i) + solve(i + 1, e);
        else
            dp[s][e] = min(dp[s][e], solve(s, i) + solve(i + 1, e));
    }
    dp[s][e] += (sum[e] - sum[s - 1]);
 
    return dp[s][e];
}
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> K;
        memset(dp, -1, sizeof(dp));
 
        for (int j = 0; j < K; j++) {
            cin >> arr[j];
            if (j == 0)
                sum[j] = arr[j];
            else
                sum[j] = sum[j - 1] + arr[j];    
        }
 
        cout << solve(0, K - 1) << endl;
    }
    return 0;
}

 

---

 

 

다이나믹 프로그래밍은, i 단계와 i - 1 단계만 정확하게 찾으면 모든 단계에서 성립한다. 고등시절, 수학적 귀납법과 같다고 할까.