[BOJ 13975] 파일 합치기 3

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

13975번: 파일 합치기 3

 

- 문제 요약

 

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다.

소설의 모든 장을 쓰고 나서는 각 장이 쓰인 파일을 합쳐서 한 개의 파일을 만든다.

이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다.

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

 

 

- 알고리즘 정리

 

문제에서 합치는 파일에 대한 제약조건이 언급되지 않았으므로 우선순위 큐를 활용해 파일을 내림차순으로 정렬하고 위에서 두 개를 꺼내와 합쳐줍니다.

그리고 합친 파일을 다시 큐에 넣어주는 과정을 파일이 1개 남을 때 까지 반복해 주면 됩니다.

(비용은 합칠 때마다 result에 넣어줍니다)

 

 

- 코드 작성

 

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

typedef long long ll;
int t,k;
ll result;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>t;
	while(t--){
		cin>>k;
		result=0;
		priority_queue<ll,vector<ll>,greater<ll> >pq;
		while(k--){
			int x;
			cin>>x;
			pq.push(x);
		}
		while(!pq.empty()){
			if(pq.size()==1){
				break;
			}
			ll mn1=pq.top();
			pq.pop();
			ll mn2=pq.top();
			pq.pop();
			result+=(mn1+mn2);
			pq.push(mn1+mn2);
		}
		pq.pop();
		cout<<result<<'\n';
	}
}

코드 제출 결과