[백준] 14241. 슬라임 합치기

14241. 슬라임 합치기

우선순위 큐를 활용한 문제였다.

값들을 우선순위 큐에 넣어 가장 큰 값 2개를 더한 값을 다시 우선순위 큐에 넣고, 곱한 값을 answer 변수에 누적 시킨다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
	int n;
	cin >> n;
	priority_queue<int> pq;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		pq.push(tmp);
	}
	int answer = 0;
	while (!pq.empty()) {
		int first = pq.top(); pq.pop();
		if (pq.empty()) break;
		int second = pq.top(); pq.pop();
		answer += first * second;
		pq.push(first + second);
	}
	cout << answer;
}