[C++] 백준 15903번 - 카드 합체 놀이

Priority Queue를 활용하는 Greedy Technique를 활용하는 문제였다.

난이도가 왜 Silver 1인지 이해를 못하겠지만

간단한 풀이는 pq를 min이 top에 오게 만든 다음 앞의 두 개를 더한 값을 두번 push해주면 된다.

그리고 크기가 매우 클 가능성이 있기 때문에 long long 자료형을 사용해야 AC를 받을 수 있다. 

#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;

priority_queue<ll, vector<ll>, greater<>> pq;
int n, m;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int x; cin >> x; pq.push(x);
	}

	while (m--) {
		ll x = pq.top(); pq.pop();
		ll y = pq.top(); pq.pop();
		ll temp = x + y;
		for (int i = 0; i < 2; i++) pq.push(temp);
	}
	
	ll ans = 0;
	while (!pq.empty()) {
		ans += pq.top(); pq.pop();
	}
	cout << ans << endl;

	return 0;
}