BOJ : 1715 카드 정렬하기

---

[BOJ 1715(G4) 리뷰]

처음에 문제를 어떻게 풀어야 할지 고민했다. 이전에 이거랑 비슷한 유형의 문제 DP문제를 풀다 포기한적이 있었는데 이문제는 다행히 DP문제가 아니라 풀수있었다.

카드를 비교할때마다 그 값들이 더해지고 최종적으로 카드가 1묶음이 남을때 그 더해지는 값의 최소값을 구해야 한다.

인풋이 10만이기에 모든 경우를 탐색하는 경우 시간초과가 나게 된다. 따라서 방법을 탐색해야하는데 문제의 조건을 천천히 생각해보자.

일단 이 문제의 최종 목표는 카드를 1묶음으로 만드는것이다. 따라서 카드 두개를 합치는 과정은 계속 되야한다.
그리고, 카드를 합치는 과정에서 비용이 발생한다. 이미 존재하는 카드 묶음의 값을 바꿀수는 없으니 우리는 카드를 합치는 과정에서 발생하는 비용을 최소화 해야 한다.

10 20 30 40 의 카드묶음이 있다고 하자.

(10+20) + (30+40) 으로 묶게되면 30+70+100 으로 총 170의 비용으로 1묶음으로 만들 수 있다.

(10+40) + (20+30) 으로 묶게되면 50+50+100 으로 총 200의 비용으로 1묶음으로 만들 수 있다.

위 예시를 보면 알듯이, 카드를 합칠때 비용이 발생하고 후에 그 카드를 더할때 또 그만큼의 비용이 발생한다.

그렇기에 우리는 카드를 합치는 비용을 최소화 해야 하므로, 최대한 작은 값들의 카드끼리 합치는것을 반복해야한다.

이러한 구조에서 유용한 자료구조가 있다. 바로 우선순위큐다.
모든 카드를 우선순위 큐에 넣어 오름차순으로 정렬한 다음에 합쳐서 나오는 카드를 다시 큐에 PUSH한다. 이때 카드는 오름차순으로 유지될 것이다. 그리고 우선순위 큐에서 가장 작은 카드 2개를 pop하여 합치고 큐에 push하는 과정을 1개의 묶음이 나올때까지 반복하면 우리는 카드를 합치는 비용을 최소화 한 값을 구할 수 있다.

/*
	21.01.06
	BOJ : 1715 카드 정리 (https://www.acmicpc.net/problem/1715)
	자료구조
*/
#include <bits/stdc++.h>
using namespace std;


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

	int N;
	cin >> N;

	priority_queue<int,vector<int>,greater<int>> Q;
	for (int i = 0; i < N; i++) {
		int val;
		cin >> val;
		Q.push(val);
	}

	int ans = 0;
	while (Q.size() != 1) {
		int n1 = Q.top(); Q.pop();
		int n2 = Q.top(); Q.pop();
		ans += n1 + n2;
		Q.push(n1 + n2);
	}

	cout << ans;
}