백준 13975 : 파일 합치기 3

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

13975번: 파일 합치기 3

 

그리디 알고리즘 문제로, 매 순간 순간에 최선의 선택을 하도록 문제를 해결하면 된다.

이 문제에서는 합치는 비용이 최소가 되도록 만드는 것이고, 가장 작은 것끼리 먼저 합치는 경우가 비용이 최소가 되는 경우이므로, 최소힙 구조를 이용하여 매 순간순간 최소값들을 구해 더해주면 된다.

 

코드로 구현하면 아래와같다.

 

#include <iostream>
#include <queue>

using namespace std;
using ll = long long;

priority_queue<ll> pq;

void solution() {
	int t, n;
	ll tmp, total, sum;

	cin >> t;
	while (t--) {
		cin >> n;
		while (n--) {
			cin >> tmp;
			pq.push(-tmp);
		}

		total = 0;
		while (pq.size() > 1) {
			tmp = -pq.top(); pq.pop();
			sum = -pq.top() + tmp; pq.pop();
			total += sum;
			pq.push(-sum);
		}
		pq.pop();

		cout << total << '\n';
	}
}

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

	return 0;
}

메모리: 14436 kb

시간: 708 ms