[백준 15903] 카드 합체 놀이 (C++)

문제 링크: https://www.acmicpc.net/problem/15903

15903번: 카드 합체 놀이

1. 주의할 점

- Int의 범위를 벗어날 수 있다

 

2. 구현

- 우선순위큐를 사용한다. 이때, 오름차순 정렬을 적용시킨다

- 값이 가장 낮은 2개를 더하는 것이 최소의 값을 가지므로 우선순위큐의 앞 2개 원소를 빼서 더하고 추가한다

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, action, val;
	long long result = 0;
	priority_queue<long long, vector<long long>, greater<long long>> pq;
	cin >> num >> action;
	for (int i = 0; i < num; i++) {
		cin >> val;
		pq.push(val);
	}
	while (action--) {
		long long first = pq.top();
		pq.pop();
		long long second = pq.top();
		pq.pop();
		pq.push(first + second);
		pq.push(first + second);
	}
	while (!pq.empty()) {
		result += pq.top();
		pq.pop();
	}
	cout << result;
	return 0;
}