[C++] 백준 11066 파일 합치기

문제 링크

---

https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

 

접근 방법

---

처음에는 정말 단순하게 오름차순으로 정렬해서 크기순으로 합치는 접근법을 사용했으나, 오답이 나왔습니다.

여러 블로그를 참고하여 인접한 파일끼리 합친다는 접근 방법을 적용하여 분할 정복 + DP 느낌으로 풀었습니다.

 

 

소스 코드

---

MAX를 501로 두고, SUM[0] = 0으로 두었습니다.

sum[a] = 0 ~ 파일 a까지의 비용의 합입니다.

cache[a][b] = 구간 [a, b]를 합치는데 드는 최소 비용입니다.

따라서 cache[a][a] = 0입니다. (합칠 구간이 없으므로)

cache[a][a+1] = sum[a + 1] - sum[a - 1]입니다.

cache[a][a + 2] = min(cache[a][a] + cache[a+1][a+2], cache[a][a+1] + cache[a+2][a+2]) + sum[a+2] - sum[a] 입니다.

더 큰 구간에 대한 문제는

cache[a][b] = min(cache[a][b], cache[a][a+mid] + cache[mid+1][b])에서 mid를 a부터 b - 1까지 반복함으로써 최소 비용을 구합니다. ( a <= b )

#include <climits>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 501
using namespace std;
int sum[MAX], cache[MAX][MAX], cost[MAX];

int divide(int low, int high) {
	if (low >= high) return 0;
	int& ret = cache[low][high];
	if (ret != -1) return ret;
	ret = INT_MAX;
	for (int mid = low; mid < high; ++mid) {
		ret = min(ret, divide(low, mid) + divide(mid + 1, high) + sum[high] - sum[low - 1]);
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T, K;
	cin >> T;
	for (int t = 0; t < T; ++t) {
		cin >> K;
		memset(sum, 0, sizeof(sum));
		memset(cache, -1, sizeof(cache));
		sum[0] = 0;
		for (int i = 1; i <= K; ++i) {
			cin >> cost[i];
			sum[i] = sum[i - 1] + cost[i];
		}
		cout << divide(1, K) << "\n";
	}
	return 0;
}

 

Visual Studio 2019 사용하였습니다.

질문, 지적 환영입니다!