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

문제 링크

1715번: 카드 정렬하기

풀이

그리디와 우선순위 큐를 이용하는 문제
처음 생각에는 그냥 오름차순 정렬해서 더해주면 되는거 아닌가? 했는데, 합치는 과정에서 정렬을 또 해줘야 했음..

1. 핵심 알고리즘은 제일 작은 카드 뭉치 두개를 합치는 것. 그래서 우선순위 큐를 사용한다.
2. 입력을 하면서 pq에 넣어준다.
3. pq가 빌 때까지 돌아가는데, 맨 위에 카드 뭉치 두개 뽑은게 n1과 n2가 된다.
   3-1. answer에 n1+n2를 더해주고 (지금까지 비교한 수 저장), 카드 뭉치 두개를 합쳐 다시 pq에 넣어준다.
   3-2. 맨 마지막 카드 뭉치를 더해주면 pq에 하나가 남을테니 카드 뭉치 하나를 뽑고 pq가 비면 break 해준다.

코드

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

int main(void)
{
	int n;
	cin >> n;

	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		pq.push(num);
	}

	int answer = 0;
	while (!pq.empty())
	{
		int n1, n2;
		n1 = pq.top(); pq.pop();
		if (pq.empty()) break;
		n2 = pq.top(); pq.pop();
		answer += n1 + n2;
		pq.push(n1 + n2);
	}

	cout << answer << endl;

	return 0;
}