백준 BOJ 13975 - 파일 합치기 3

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

13975번: 파일 합치기 3

우선순위 큐 사용 문제.

하나의 우선순위 큐에 임시파일을 포함한 모든 파일들을 저장해놓고,

실시간으로 가장 비용이 작은 두개의 파일을 합쳐서 하나의 임시파일로 만들어주면 된다.

이 과정을 파일이 하나만 남을때까지 반복해주면 되고,

 

전체 시간복잡도는 O(KlogK) 이다.

 

입력되는 수의 갯수가 1e6으로 꽤나 많으니 fastio를 써야 할 듯 하고,

수의 범위가 int값을 넘어가니까 long long 형으로 선언해준 다음

C언어 기준 PQ의 우선순위를 정 반대로 바꿔주어야 한다.

 

PQ의 우선순위를 바꾸는 두 가지 방법으로

첫번째는 greater<ll> 을 사용하는 방법이 있고,

두번째는 모든 값에 -1을 곱해서 음수로 저장했다가 꺼낼때 다시 -1을 곱해주는 방법이 있다.

 

취향껏 사용해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int T;
	cin >> T;
	while(T--){
		priority_queue<ll, vector<ll>, greater<ll>> pq;
		ll N,K;
		ll ans = 0;
		
		cin >> N;
		for(int i=0; i<N; i++){
			cin >> K;
			pq.push(K);
		}
		
		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;
}