BOJ#11066 파일 합치기 (Merging Files)

BOJ#11066 파일 합치기 (Merging Files)

 * 문제

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

* 풀이

수열이 주어지고, 인접한 숫자는 합칠 수 있습니다. 합치는 비용은 두 수의 합이고, 전체 수를 합치는데 필요한 최소 비용을 구하는 문제입니다.

,

동적계획법 (Dynamic Programming)을 이용합니다. 

먼저 dp의 정의를 세워보면

dp[i][j] : 수열에서 i번째~j번째 수까지 합치는데 필요한 최소 비용

,

따라서 아래와 같은 수열이 존재할 때

null 40 30 30 50

위 정의에 따르면 

자기 자신인 경우에는 합칠 수 없으므로

dp[1][1] = 0, dp[2][2] = 0 ... 이 될 것입니다.

또한 인접한 수에 대해서는

dp[1][2] = 70, dp[2][3] = 60, dp[3][4] = 80와 같이 될 것입니다.

,

동적계획법은 주어진 문제를 여러 하위 문제로 나눠서 푸는 것이라고 했으니까

우리가 원하는 값인 dp[1][4]를 위와 같이 하위 문제들로 나누어 보면 되겠습니다.

1) null (40) (30 30 50)

2)     null (40) {(30) (30 50)}

3)     null (40) {(30 30) (50)}

4) null (40 30) (30 50)

5) null (40 30 30) (50)

6)     null {(40) (30 30)} (50)

7)     null {(40 30) (30)} (50)

즉, 위 경우로 나눌 수 있고

7가지의 경우의 값 중 최소값이 원하는 값이 됩니다.

,

이제 최종적으로 점화식을 구성해 보겠습니다.

(i <= k < j) 일 때

dp[i][j] = min(dp[i][k] + dp[k+1][j])  +  (i~j 수열의 합)

,

점화식을 위 2번째 경우에 적용해 보면

dp[1][4] = dp[1][1] + dp[2][4] + (40 + 30 + 30 + 50)

              = dp[1][1] + {dp[2][2] + dp[3][4] + (30 + 30 + 50)} + (40 + 30 + 30 + 50)

              = 0           + 0            + 80         + (110)                  + (150)

              = 340

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%2311066_MergingFiles

* 참고

http://blog.myungwoo.kr/98