[BOJ] 카드 정렬하기 1715번

지난번에 풀어본 적이 있었던 문제였는데 오랜만에 보니까 확실히 까먹게 되네요. 우선순위 큐를 사용해서 풀었습니다.

• 우선순위 큐를 선언할 때 greater를 같이 넣어줌으로서 내림차순 정렬(queue내부에서 내림차순, 따라서 순서대로 top을 출력보면 가장 마지막에 나온 숫자가 가장 크다)이 되게 해주었습니다. <functional>은 greater를 사용하기 위해 선언해주었습니다. 
• 입력을 받으면서 우선순위 큐에 바로바로 push를 합니다.
• while문에서 pq.size()가 1보다 클 때까지 반복을 해줍니다. 1보다 클 때까지로 조건을 정한 이유는 큐에서 두 개의 수를 뽑아 더한 뒤에 마지막에 push를 해주기 때문에 result에 최종 답이 담기게 되어도 pq에는 하나의 값이 더 남게됩니다.

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

using namespace std;

int main(void) {
	priority_queue<int,vector<int>,greater<int>> pq;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		pq.push(a);
	}
	
	int sum=0, result=0;
	while (pq.size() > 1) {
		int first = pq.top(); pq.pop();
		int second = pq.top(); pq.pop();
		sum = first + second;
		result += sum;
		pq.push(sum);

	}

	cout << result;

}