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

이 문제는 카드 묶음이 $N$개 주어질 때, 카드를 합치는 경우 최소의 비교 횟수를 구하는 문제이다.

카드의 수가 $A$와 $B$인 두 묶음을 합치려면, 비교 횟수는 $A + B$가 된다.

하지만, 카드 묶음이 여러 개이므로 카드 묶음이 1개가 될 때 까지, 2개씩 선택해서 하나로 합쳐주어야 한다.

우리는 최소값을 구해야 한다. 그렇다면, 매 과정에서 최소로 비교를 하도록 카드 묶음을 선택하면 될 것이다.

따라서, 카드 갯수가 가장 적은 2개의 묶음을 선택해야 한다.

우리는 카드 묶음을 선택하는 과정을 $N - 1$번 반복하기 때문에, 전체를 비교해서 최소인 2개를 선택하면 시간복잡도가 $O(N^2)$이 된다.

배열에 이분 탐색을 이용해서 삽입과 삭제를 처리한다 하더라도, 배열 자체의 삽입, 삭제 시간 복잡도가 $O(N)$이므로 전체 시간 복잡도는 $O(N^2logN)$이 된다.

따라서, 배열이 아닌 트리를 사용해야 한다.

우리는 그저 매 과정에서 최소값만을 찾기 원하기 때문에 priority_queue만으로도 충분할 것이다.

정답은 최대 $1668928000$으로 대략 17억정도가 된다. 따라서 int로 표현이 가능하다.

#include <bits/stdc++.h>
using namespace std;

int n;
priority_queue<int, vector<int>, greater<>> pq; //최소힙

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

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

	int ans = 0;
	while (pq.size() > 1) {
		int a, b;
		a = pq.top(), pq.pop(), b = pq.top(), pq.pop();
		ans += a + b;
		pq.push(a + b);
	}

	cout << ans;
}