[백준] 13975번 파일 합치기3

파일을 두 개씩 계속 합해서 가장 작은 값이 나오도록 하는 문제이다. 어떻게 하면 가장 작게 합칠 수 있을까??

 

문제해결방법

1. 우선순위 큐를 사용한다.

2. 가장 작은 값 두 개를 합치고 다시 우선순위 큐에 집어넣는다.

3. 두 개를 합친 값을 sum에 저장한다.

 

30 30 40 50 이렇게 있으면

가장 작은 두 개를 합치면 30+30이다.

합치고 다시 큐에 집어넣으면

큐의 상태는 40 50 60이 된다.

sum의 값은 60이다.

이 순서대로 계속 진행하면

40+50=90

sum=60+90

60 90(큐 상태)

60+90=150

sum=150+150

큐가 비었으면 while문 종료

 

30 30 40 50 -> 40 50 60 -> 60 90 -> 150

 

#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
	int T=0;
	cin>>T; 
	for(int i=0; i<T; i++)
	{
		long long sum=0;
		int N=0;
		cin>>N;
		priority_queue<long long> pq;
		for(int i=0; i<N; i++)
		{
			long long num=0;
			cin>>num;
			pq.push(-num);
		}
		
		while(!pq.empty())
		{
			long long num1=-pq.top();
			pq.pop();
			
			long long num2=-pq.top();
			pq.pop();
			//cout<<num1+num2<<endl;
			sum=sum+num1+num2;
			if(pq.empty())
			{
				cout<<sum<<endl;
				break;
			}
			pq.push(-(num1+num2));
		}
	}
	return 0;
}