카드 정렬하기 (1715)

카드 묶음을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

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

priority_queue<int, vector<int>, greater<int>> PQ;

int N;
int Total = 0;

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int Num;
		cin >> Num;
		PQ.push(Num);
	}

	while (PQ.size() != 1)
	{
		int First = PQ.top();
		PQ.pop();
		int Second = PQ.top();
		PQ.pop();
		int Sum = First + Second;
		Total += Sum;
		PQ.push(Sum);
	}

	cout << Total;

	return 0;
}