[BOJ] 1715번_카드 정렬하기_우선순위 큐 (C++)

[문제]

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

A와 B라는 두개의 정렬된 숫자 카드 묶음이 있을 때, 두 묶음을 합쳐서 하나로 만드려면
A+B번 비교를 해야한다. N개의 숫자 카드 묶음이 존재할 때, 최소 몇 번의 비교로 하나의 묶음으로 합칠 수 있는지 구하는 문제이다.

[사용 알고리즘]

우선순위 큐

[풀이 핵심]

• 문제를 보면 알 수 있듯이 결국 가장 작은 묶음 2개를 골라 하나로 합치는 과정을 반복하면 답을 구할 수 있다.
• 이 때 우선순위 큐를 이용하면 시간초과 없이 간단하게 해결할 수 있다.

[코드]

//boj1715번_카드 정렬하기_우선순위 큐

#include<iostream>
#include<queue>

using namespace std;

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

	priority_queue<int, vector<int>, greater<int>> q;

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

	int result = 0;

	while (true) {
		if (q.size() == 1) {
			break;
		}

		int A = q.top();
		q.pop();

		int B = q.top();
		q.pop();

		q.push(A + B);
		result += (A + B);
	}

	cout << result;

	return 0;
}