[백준] 1715 카드 정렬하기

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

우선순위 큐를 이용하는 전형적인 문제였다.

 

예전에 어디서 푼? 기억이 있어서 금방 풀었다.

 

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

using namespace std;

int main() {
	int N;
	cin >> N;

	//우선순위 큐 : 큰 수 부터
	priority_queue<int> arr;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push(-num);
	}

	int sum = 0;

	if (N == 1)
	{
		cout << sum;
	}
	else
	{
		while (!arr.empty()) {
			int x = -arr.top();
			arr.pop();

			if (arr.empty()) {
				cout << sum;
			}
			else
			{
				int y = -arr.top();
				arr.pop();
				sum += (x + y);
				arr.push(-(x + y));
			}
		}
	}
	
}

원래 우선순위 큐는 큰 수부터 값이 정렬돼있기 때문에 - 값을 해주어 작은 수 부터 값을 이용할 수 있게 하였다. 

 

다음에 이런 유형이 나오면 우선순위 큐를 사용하자