[C++] 백준 - 1715번 : 카드 정렬하기

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

1715번: 카드 정렬하기

문제

---

풀이

최소 비교 횟수를 구하기 위해선, 가장 작은 묶음 끼리 비교를 진행해야 합니다.

가장 작은 카드 묶음을 빠르게 구하기 위해서, Heap 구조로 되어있는 우선순위 큐(Priority Queue)를 사용합니다.

 

우선순위 큐에 모든 카드 묶음을 넣은 후, 우선순위가 높을 두 개를 빼서 더한 후 그 비교 횟수를 결과에 추가하고 비교하여 나온 새로운 카드 뭉치의 개수를 다시 우선순위 큐에 넣어줍니다.

다시 넣어주는 이유는 새로나온 카드 뭉치 또한 비교의 대상이 되기 때문입니다.

예) 10 10 10 10 인 경우, 10 10 을 꺼내어 더한 20개의 카드 뭉치를 우선순위 큐에 넣어주면 10, 10, 20 으로 정렬이 되고 10 10 을 다시 꺼내어 20개의 카드뭉치를 큐에 넣으면 20 20 이 됩니다. 최종적인 비교 횟수는 (10+10) + (10+10) -> 80 이 됩니다.

정리하자면

1. 우선순위가 높은 카드 뭉치 A, B를 꺼내어 더합니다.

2. 더한 값은 곧 새로운 카드뭉치의 개수가 되므로 이를 우선순위 큐에 넣어줍니다.

3. 더한 값은 A+B의 비교횟수가 되므로 이를 결과에 더해줍니다.

4. 위의 과정을 우선순위 큐의 원소가 1 이하가 될 때 까지 반복해줍니다.

 

여기 4번 과정에서 큐의 원소가 0이 아닌 1 이하가 될 떄 까지 진행하는 경우는

카드 뭉치가 1개밖에 없을 경우에는 같이 합칠 카드 뭉치가 없으며, 이는 곧 비교 대상이 없다는 뜻이므로 비교를 진행하지 않게 됩니다.

 

---

코드

#include<iostream>
#include<queue>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

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

	int res = 0;
	int a, b = 0;
	for (int i = 0; i < n; i++) {
		a = pq.top();
		pq.pop();
		if (!pq.empty()) {
			b = pq.top();
			pq.pop();
			pq.push(a + b);
			res += (a + b);
		}
	}
	cout << res;
	return 0;
}