<Baekjoon> #11066 Dynamic Programming_merging files c++

#11066 merging files
참고

1. dp[x][y] =file[x]에서 file[y]까지 합치는데 드는 최소비용
   마지막에 구해야 하는 것은 dp[1][K]가 된다

2. sum[x]은 file[1]부터 file[x] 까지의 부분합이다.
   sum[x]=sum[x-1]+file[x] 이다.

예를 들어 아래와 같이 file의 예시가 있을 때, 전체 부분을 작은 부분으로 나누어 구해서 마지막에 dp[1][K]를 구할 것인데, i,j,k 총 세 개의 변수를 두고 삼중 for문을 돌며 구할 것이다.

for (int i = 1; i <= K; i++) {
	for (int j = 1; j <= K - i; j++) {
		dp[j][i + j] = INF;
		for (int k = j; k < i + j; k++) {
			dp[j][i + j] = min(dp[j][i + j], 
				dp[j][k] + dp[k + 1][i + j] + sum[i + j] - sum[j- 1]);
				}
			}
		}

• i : 지금 구할 subproblem의 총 길이
• j : 지금 구할 subproblem의 시작 지점
• k : 지금 구할 subproblem을 두 부분으로 나누는 지점으로, (j<=k<i+j)
  위와 같은 경우에는 k에 따라서
  {21}, {3,4,5,35,5,4}
{21,3}, {4,5,35,5,4}
{21,3,4} {5,35,5,4}
{21,3,4,5} {35,5,4}
{21,3,4,5,35} {5,4}
{21,3,4,5,35,5} {4}
  으로 나누어지고 다시 아래와 같이 subproblem들을 호출한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 500;
const int INF = 1e8;
int dp[MAX][MAX];

int main() {
	int T, K;
	vector<int> file;
	vector<int>sum;
	cin >> T;
	while (T--) {
		cin >> K;
		file = vector<int>(K+1);
		sum = vector<int>(K+1, 0);

		for (int i = 1; i <= K; i++) {
			cin >> file[i];
			sum[i] = sum[i - 1] + file[i];
		}

		for (int i = 1; i <= K; i++) {
			for (int j = 1; j <= K - i; j++) {
				dp[j][i + j] = INF;
				for (int k = j; k < i + j; k++) {
					dp[j][i + j] = min(dp[j][i + j], 
						dp[j][k] + dp[k + 1][i + j] + sum[i + j] - sum[j- 1]);
				}
			}
		}
		cout << dp[1][K] << "\n";
	}
	return 0;
}