백준13975 파일 합치기 3

작성일 | In

문제 링크

  • http://icpc.me/13975

사용 알고리즘

  • 그리디
  • 허프만 코드

시간복잡도

  • O(N log N)

풀이

크기가 작은 두 파일을 골라 합쳐주는 것을 반복하면 됩니다.
허프만 코드(허프만 인코딩)처럼 구현하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> v;

void solve(){
	int n; cin >> n; v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i];

	ll ans = 0;
	priority_queue<ll> pq;
	for(auto i : v) pq.push(-i);

	while(pq.size() >= 2){
		ll a = -pq.top(); pq.pop();
		ll b = -pq.top(); pq.pop();
		ans += a + b;
		pq.push(-(a+b));
	}
	cout << ans << "\n";
}

int main(){
	int t; cin >> t;
	while(t--) solve();
}