[C++] 백준 1715번: 카드 정렬하기

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

우선순위 큐 분류에 들어가 있는 골드4 난이도의 문제였다.

 

이 문제 같은 경우엔 두 묶음을 골라 합치면 비교 횟수가 줄어 드는 것을 생각하고 풀면 쉽게 풀리는 문제였다.

 

최소 우선 순위 큐에 각 카드 묶음들을 넣어주고 계속 2개씩 꺼내어 더한 후 다시 넣어주는 식으로 구현하였다.

 

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

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

int main() {
	int n, x, ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		pq.push(x);
	}
	while (pq.size() > 1) {
		int a = pq.top();
		pq.pop();
		int b = pq.top();
		pq.pop();
		ans += a + b;
		pq.push(a + b);
	}
	cout << ans;
	return 0;
}