백준 - 13975번 : 파일 합치기 3 (C++)

풀이 방법 : 우선 순위 큐

비슷한 문제가 참 많은 문제

현재 있는 파일 중에서 가장 작은 두 개를 골라 합치는 것을 반복하면 가장 최소 비용으로 파일을 합칠 수 있다.
그러므로 우선순위 큐를 통해 최솟값 두개를 뽑아내서 합을 구하고 비용에 누적 시킨 뒤 합친 파일을 다시 우선 순위 큐에 삽입해주는 것을 반복하면 된다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	int T;
	cin >> T;

	for (int i = 0; i < T; ++i)
	{
		int N;
		cin >> N;

		long long Sum = 0;
		priority_queue<long long, vector<long long>, greater<long long>> pqNum;

		for (int j = 0; j < N; ++j)
		{
			long long Num;
			cin >> Num;
			pqNum.push(Num);
		}

		while (!pqNum.empty())
		{
			if (pqNum.size() == 1)
			{
				cout << Sum << '\n';
				break;
			}

			long long Tmp = 0;

			Tmp += pqNum.top();
			pqNum.pop();
			Tmp += pqNum.top();
			pqNum.pop();

			Sum += Tmp;
			pqNum.push(Tmp);

		}
	}
}

너무 전형적인 문제라 산술 오버플로만 조심하면 어려울게 없는 문제