백준 BOJ 13975 파일합치기3 풀이

사용언어

Visual studio 2019 C++

원래 이문제를 풀려고 했던건 아닌데… 11066번 파일합치기 문제를 잘못이해 했는데 이 문제의 답이라서.. 풀게된…문제………

[13975 풀이]

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

#define endl "\n"
using namespace std;

vector<long long> v;

void init() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

void file() {
	int k;
	cin >> k;
	v.resize(k);

	for (int i = 0; i < k; i++)
		cin >> v[i];

	long long result = 0;

	priority_queue<long long> pq;
	for (int i = 0; i < k; i++)
		pq.push(-v[i]);

	while (1) {
		if (pq.size() == 1)
			break;
		long long a = -pq.top();
		pq.pop();
		long long b = -pq.top();
		pq.pop();

		result += (a + b);
		pq.push(-(a + b));

	}
	cout << result << endl;
}

int main() {
	init();
	int t; cin >> t;
	while (t--)
		file();
}