[백준] 11066 파일합치기

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

11066번: 파일 합치기

---

DP로 해결해야 하는 문제이기 때문에 점화식을 세우는 것이 중요합니다. 점화식은 아래와 같습니다

DP[i][j]: files[i]에서 files[j]까지 합치는 총 비용

 

1 2 3 4 의 파일들이 존재할 때 files[0]에서 files[3]까지 파일을 합치는 방법은 여러가지가 있습니다.

 

(1 + 2) + (3 + 4)

1 + ((2 + 3) + 4)

(1 + (2 + 3)) + 4 

....

 

따라서 시작 지점과 끝 지점의 파일을 모두 더할 때 중간 계산 중 최소 값을 구해야 합니다. 이를 수도 코드로 나타내면 아래와 같습니다.

for j <- start to end-1:
    dp[start][end] = 
         MIN(dp[start][end], dp[start][j] + dp[j+1][end] + (arr[start] + ... + arr[end]))

dp[start][j] + dp[j+1][end]

위 식은 files[start] ~ files[j]까지와 files[j+1] ~ files[end]까지 비용의 합을 의미합니다.

arr[start] + ... + arr[end]

위 식은 file[start] ~ file[end] 까지 합을 의미합니다. 누적 합 알고리즘을 사용하면 쉽게 나타낼 수 있습니다. 

 

예를들어, (1 + 2) + (3 + 4)의 경우 dp[0][1] = 3, dp[2][3] = 7이 됩니다. 그리고 file[0] ~ file[3]의 합은 10입니다.

따라서 위 방식의 최종 비용은 3 + 7 + 10 = 20이 됩니다.

 

이렇게 구한 비용들을 모두 비교하여 최소값을 구하면 문제를 해결할 수 있습니다.