BOJ - 11066 ) 파일 합치기

 3중 for 문을 활용하여 풀어야 하는 동적 프로그래밍 문제이다. 파일은 연속되는 것들만 합치기가 가능하며, 파일을 계속 합치며 도출 되는 비용이 최소가 되도록 알고리즘을 구성해야 한다.

 

알고리즘 풀이에 쓰이는 배열

 

1. dp[i][j] 배열은 i 부터 j 장까지 최소 비용이라고 정의하고, 첫 번째 장부터 마지막 장까지 최소 비용의 값을 갱신하며 값을 도출한다. 이러한 정의로 다음과 같은 점화식을 도출할 수 있다.

2. cost[i] 배열은 주어진 파일을 합치는 비용을 저장하는 배열이다.

3. sum[i] 배열은 i 까지의 파일을 합하는데 필요한 비용을 나타낸다. 예를 들어, 첫 번째 경우 예제 입력에서 주어진 값을 사용한다면, sum[2] = 70 이고 sum[i] = sum[i-1] + cost[i] 로 나타낼 수 있다.

 

배열을 사용한 점화식 성립

 

dp[i][i] = cost[i] = sum[i] - sum [i-1] ( i 장 부터 i 장 까지의 최소 비용으로, 주어진 cost[i] 와 값이 같다. )

dp[i][i + 1] = sum[i+1] - sum[i-1]

dp[i][i + 2] = min(dp[i][i] + dp[i+1][i+2], dp[i][i+1] + dp[i+2][i+2]) ( 주어진 인덱스 상으로 1 + ( 2+3) 의 크기와 (1+2) + 3 과의 크기를 비교하여 최소의 값을 선택한다.)

위의 식에 따라서, 예를 들어 총 4개의 장이 있다고 가정하면 비교해야하는 경우의 수는 다음과 같다.

 

dp[1][1] + dp[2][4]

dp[1][2] + dp[3][4]

dp[1][3] + dp[4][4]

 

따라서, 점화식은 다음과 같이 성립이 가능하다.

dp[i][j] = dp[i][k] + dp[k+1][j] + sum[i][j] (k 는 i<=k<j 를 만족한다.)