백준 - 카드 정렬하기 (1715) [C++]

이 문제는 그리디 알고리즘, 우선순위 큐를 사용하여 풀었다.

 

A + B가 최소가 되게 하는 두 카드를 매번 고르면서, 카드들이 1개만 남을 때까지 반복하면 된다.

 

이 때 최소가 되게 하는 두 카드를 O(log N) 시간에 뽑을 수 있는 자료구조는 우선순위 큐이므로, 이를 이용하여 풀었다.

#include <iostream>
#include <queue>

using namespace std;

#define MAX 100000

int N;
int cards[MAX];

int solve() {
	priority_queue<int, vector<int>, greater<int>> minPQ;

	for (int i = 0; i < N; i++) {
		minPQ.push(cards[i]);
	}

	int result = 0;
	while (minPQ.size() > 1) {
		int a = minPQ.top();
		minPQ.pop();
		int b = minPQ.top();
		minPQ.pop();

		result += (a + b);

		minPQ.push(a + b);
	}

	return result;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;

	if (N == 1) {
		cout << 0 << '\n';
		return 0;
	}

	for (int i = 0; i < N; i++) {
		cin >> cards[i];
	}

	int answer = solve();

	cout << answer << '\n';

	return 0;
}