11066 : 파일 합치기 (Dynamic Programming) [C,C++]

DP 문제는 DP 문제인 줄 알아도 적용을 잘 못하겠다..

더 많이 풀어봐야겠다.

A4용지 4장을 끄적이다 결국 구글링 찬스를 사용했다!

최소 행렬 곱셈 문제와 유사한 문제

앞부터 뒤까지 하나 하나 다해보고 그것 중의 최솟값을 구하는 문제이다.

최소 행렬 곱셈의 식은 DP[i][j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + d(i-1) * d(k) * d(j))

파일 합치기 식은 DP[i][j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + sum[i][j]

왜 최소 행렬 곱셈과 비슷하냐면 파일 합치기 문제는 앞과 뒤만 비교하고

교환법칙이 성립하지 않는다.

for (int i = 0; i <= Size; i++)
{
 for (int n = 1; n <= Size; n++)
 {
  int m = n + i;

  if (n == m || m > Size)
   continue;

  DP[n][m] = INT_MAX;

  for (int k = n; k < m; k++)
   DP[n][m] = min(DP[n][m], DP[n][k] + DP[k + 1][m] + Sum[m] - Sum[n - 1]);
 }
}

<소스 코드>

*Source of the problem = https://www.acmicpc.net/problem/11066

*문제 출처 : BAEKJOON ONLINE JUDGE