백준 1715번 카드 정렬하기 문제풀이(C++)

백준 1715번 카드 정렬하기

아이디어

우선순위 큐로 두개 씩 순차적으로 더해나간다

문제해결

#include<bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	priority_queue<long long, vector<long long>, greater<>> pq;
	int n; cin >> n;
	for (int i = 0; i < n;i++) {
		int card; cin >> card;
		pq.push(card);
	}
	long long sum = 0;
	long long left = 0, right = 0;
	while (!pq.empty()) {
		left = pq.top();pq.pop(); 
		if (pq.empty()) {
			sum += left;
			break;
		}
		right = pq.top();pq.pop();
		sum += (left + right);
		if(!pq.empty())
			pq.push((left + right));
	}
	if (n > 1)
		cout << sum << '\n';
	else cout << 0 << '\n';
	return 0;
}