BOJ - 파일 합치기(C++)

문제 출처: https://www.acmicpc.net/problem/11066

문제 난이도

Gold 3

문제 접근법

1~N까지의 파일 최소값을 구하는 문제다.
이중 배열 DP를 선언하고 결과적으로 DP[1][N]인 값을 도출하면 된다.
여기서 중요한 포인트는 누적합을 이용하는 것과 1~N까지라면 중간에 부분합을 구해서 가장 최소값을 구해서 갱신해야 한다.
그리고 구하고자하는 페이지 범위의 최소값과 더해야하는 누적값을 비교해서 최소값을 갱신한다.
즉, 문제 속에서의 X1 C1의 역할이다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

int dp[501][501];
int sum[501];

int main() {
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		vector<int> file(N + 1);
		for (int i = 1; i <= N; i++) {
			cin >> file[i];
		}
		for (int i = 1; i <= N; i++) {
			sum[i] = sum[i - 1] + file[i];
		}
		for (int i = 1; i <= N; i++) {
			for (int start = 1; start <= N - i; start++) {
				int end = start + i;
				dp[start][end] = INF;
				for (int mid = start; mid <= end; mid++) {
					dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start - 1]);
				}
			}
		}
		cout << dp[1][N] << "\n";
	}
	return 0;
}

피드백

DP라고 하기엔 점화식이나 작은 부분을 찾아 DP를 만들수가없었다. 그래서 다른 사람 글을 참고해서 코드를 작성했고 이해하는데도 시간이 꽤 걸렸다.
특히 dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start - 1] 여기를 왜 한 번 더 더해야하는지 의문이었다.