[BOJ] 파일 합치기

[BOJ] 파일 합치기

Problem URL : 파일 합치기

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

using namespace std;

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

int main() {
	int TC;
	cin >> TC;
	for(int tc = 1; tc <= TC; tc++) {
		int N;
		cin >> N;
		int file;
		for (int i = 1; i <= N; i++) {
			cin >> file;
			sum[i] = sum[i - 1] + file;
		}

		for (int i = 1; i < N; i++) {
			for (int start = 1; start <= N - i; start++) {
				int end = start + i;
				dp[start][end] = INF;
				int SUM = sum[end] - sum[start - 1];
				for (int mid = start; mid <= end; mid++) {
					dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid + 1][end] + SUM); // [1]
				}
			}
		}
		cout << dp[1][N] << "\n";
	}
	return 0;
}

Comments

[1] 어떤 순서로 (어떤 mid 기준으로) 합쳐야 dp가 최소가 될지 결정하는 과정이다.

처음에는

임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 ‘연속’이 되도록 파일을 합쳐나가고

에서의 연속 조건을 인지하지 못해서 priority queue로 풀었는데 틀렸었다. 문제를 잘 읽도록 하자!