백준 1715 : 카드 정렬하기

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

1715번: 카드 정렬하기

 

간단하게 설명하면 카드 뭉치들이 여러개가 있는데 이 중 두개의 카드 뭉치를 골라 하나로 합치는데 드는 힘이 두 카드뭉치들의 카드 수의 합이라고 할 때, 최소의 힘으로 모든 카드 뭉치를 합치는 문제이다.

 

우선순위 큐를 사용하여 현재 상태에서 가장 카드 수가 적은 카드 뭉치 두 개를 꺼내 합치고 그 결과로 생긴 하나의 카드뭉치를 다시 우선순위 큐에 넣어 반복하는 방법으로 문제를 해결했다.

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	int tmp, ans = 0;
	priority_queue<int> pq;

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

	//pq에서 두 개씩 꺼내서 합치고 최종적으로 하나가 남으므로 pq.size() > 1인 동안에
	while (pq.size() > 1) {
		tmp = 0;
		tmp += pq.top(); pq.pop();
		tmp += pq.top(); pq.pop();

		ans -= tmp;
		pq.emplace(tmp);
	}

	cout << ans;
	return 0;
}

메모리: 2916 kb

시간: 20 ms