백준 13975 파일 합치기 3

 

출처 : www.acmicpc.net/problem/13975

 

문제

여러 장의 소설이 각각 다른 파일에 저장되어 있다.

소설을 모두 쓰면, 각 장이 쓰인 파일을 합쳐 최종적 완성본인 단 하나의 파일만을 남겨두어야 하는데,

이 과정에서 두 개의 파일을 합치고, 합친 파일이나 다른 두 개의 파일을 계속 두 개씩 합쳐나가야 한다.

두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총합을 계산하시오.

 

ex. 40, 30, 30, 50 -> 40, (30 + 30), 50 -> (40 + 50), 60 -> 90, 60 -> 150

이때, 비용은 60 + 90 + 150 = 300 이 된다.

 

풀이

우선순위 큐를 사용하는 아주 웰 노운 한 문제입니다.

참고로 이 문제는 11066번 파일 합치기 1 문제와 비슷하지만 "파일을 합치는 순서에 제약이 없을 때" , 즉 아무 파일이나 두 개씩 붙이면 되는 문제일 경우에만 우선순위 큐를 사용할 수 있습니다.

 

결론부터 말하자면, 여러 파일을 합쳐 하나로 만들 때 합치는 최소 비용을 구하기 위해선 모든 파일에 대해서 가장 크기가 작은 두 파일들을 계속해서 합쳐주면 됩니다.

 

위 예시처럼, (40, 30, 30, 50) 총 4개의 파일이 있다고 가정해봅시다.

크기가 큰 파일을 먼저, 작은 파일을 먼저 합칠 때 두 가지 경우를 직접 풀어 써보면

 

1) 큰 파일을 먼저 (굵은 글씨가 현재 합쳐지는 파일)

40, 30, 30, 50 -> (40 + 50), 30, 30 -> (40 + 50 + 30), 30 -> (40 + 50 + 30+ 30) -> 150

이때, 비용은 90 + 120 + 150 = 360 이 됩니다.

2) 작은 파일을 먼저

40, 30, 30, 50 -> 40, (30 + 30), 50 -> (40 + 50), (30 + 30) -> (40 + 50) + (30 + 30) -> 150

이때, 비용은 60 + 90 + 150 = 300 이 됩니다.

 

자세히 보면, 앞에서 먼저 합쳐진 파일들은 한 파일로 묶어야 하기 때문에 뒤에서도 반복해서 합쳐질 수밖에 없습니다. 따라서 큰 파일을 먼저 합쳐버리면 나중에 또 그만큼의 비용이 들기 때문에 최대한 나중에 합쳐주는 게 좋습니다.

 

우리는 이 파일들 중 가장 작은 두 파일들을 찾기 위해서 우선순위 큐를 이용합니다.

방법은 간단하게, 우선 파일의 크기를 모두 우선순위 큐(min heap)에 담고, 작은 파일 두 개를 빼서 더한 후 다시 우선순위 큐에 담는 과정을 크기가 1이 될 때까지 반복합니다.

소스 코드(.cpp)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	{
		priority_queue<ll, vector<ll>, greater<ll> >pq;
		int k; cin >> k;
		for (int i = 0; i < k; i++) {
			int x; cin >> x;
			pq.push(x);
		}
		ll ans = 0;
		while (pq.size() > 1) {
			ll a = pq.top(); pq.pop();
			ll b = pq.top(); pq.pop();
			ans += (a + b);
			pq.push(a + b);
		}
		cout << ans << "\n";
	}
	return 0;
}