[BAEKJOON] 11066 파일 합치기 (C++)

문제 링크

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

11066번: 파일 합치기

 

문제

파일의 크기가 정수로 주어진다.

파일 두개를 합치는데 필요한 비용은 크기의 합이다.

모든 파일을 합치는데 드는 최소비용을 찾는 문제

 

풀이

처음엔 그리디하게 풀어보려고 했다.

결국 합치는 과정에서 먼저 합친 파일은 그만큼 합에 누적되기 때문에, 작은 크기의 파일들을 최대한 활용하면 되겠다고 생각했다. 

반례가 너무 많아 통과가 안 돼서 포기.

결국 분류대로 DP를 이용해야했는데, 도저히 생각이 안 났다. 그래서 풀이 가이드를 찾아봤는데 그럼에도 불구하고 구현을 어떻게 해야할지 잘 생각을 못 했다. 풀이를 이해하고도 구현이 헷갈린 걸 보면 요즘 PS를 너무 안 했나보다.

 

풀이는 다음과 같다.

2차원 배열을 이용해 값을 기록한다.

dp[i][j] 는 i번째부터 j번째까지 파일을 합치는데 드는 최소 비용이다.

 

만약 i ~ j 번째 사이에 존재하는 구간들 ex)  i~k , k~ j (i< k < j)

이 이미 잘 계산돼있다면 i~j번째 까지 파일들을 합하는데 드는 비용의 최소값을 계산할 수 있다.

 

따라서 

dp[i][i + k] = min(dp[i][i+j] + dp[i+j+1][i + k] + sum[i + k] - sum[i - 1], dp[i][i + k]);

 

다음의 점화식을 이용한는데,

i는 시작지점, k는 구하는 구간의 길이, j 는 i~ i+k 사이를 돌며 해당 구간을 어떻게 2개로 나눴을 때 최소값이 발생하는지 확인한다.

 

즉 1~N번째 까지의 파일을 합치는데 드는 최소비용은 어떻게 중간지점을 나눠가면서 최소비용이 발생하는 지점을 찾는지가 관건이다.

 

참고 블로그: https://cocoon1787.tistory.com/317

코드

#include <bits/stdc++.h>

#define endl "\n"

typedef long long ll;
using namespace std;

int N;
long long A[505];
long long dp[505][505];
long long sum[505];

void Solve() {
	cin >> N;

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

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

	cout << dp[1][N] << endl;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	//freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	while (T-- > 0) {
		Solve();
	}
	return 0;
}