[C/C++] 백준 1715, 정렬

문제

1715번: 카드 정렬하기 (acmicpc.net)

1715번: 카드 정렬하기

코드

#include <queue>
#include <iostream>

using namespace std;

int main() {
	priority_queue<int> card;
	int N, result = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int t;
		cin >> t;
		card.push(-t);
	}

	while (card.size() > 1) {
		int first = -card.top();
		card.pop();
		int second = -card.top();
		card.pop();

		int sum = first + second;
		result += sum;
		card.push(-sum);
	}

	cout << result;
}

풀이

1. 처음엔 가장 작은 수 두 개를 먼저 고르고 그 다음엔 가장 작은 수 두 개를 더한 값과 세 번째로 작은 수를 더하는 코드를 구현해야 한다.

2. 따라서 작은 값을 먼저 반환하는 우선순위 큐를 활용하여 코드를 구성한다.

3. 카드가 한 장만 남을 때까지 실행되는 while문 내에서 first에는 가장 작은 수를 넣은 다음 pop, second에는 그 다음으로 작은 수를 넣은 다음 pop하여 두 값을 더하고(sum) 다시 우선순위 큐에 push

4. 결과값이 될 result에 sum을 더한다.