15903번 카드 합체 놀이 문제풀이(C++)

15903번 카드 합체 놀이

아이디어

x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)

계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

---

카드를 두장 뽑아 더한 값으로 뽑은 두장의 카드 값을 대체한다 -> 가장 작은 수의 카드 두개를 뽑자 -> 우선순위 큐를 사용하자 (※ 값의 최대값 == 1,000,000 => int값 초과)

// 우선순위 큐 내림차순
priority_queue<long long, vector<long long>, greater<>> pq;

// 단순하게 두장 뽑아서 더한 값을 다시 두번 넣는 코드
ll sum = pq.top();
pq.pop();
sum += pq.top();
pq.pop();
pq.push(sum);
pq.push(sum);

문제풀이

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	priority_queue<ll, vector<ll>, greater<>> pq;
	for (int i = 0; i < n; i++) {
		int num; cin >> num;
		pq.push(num);
	}
	while (m--) {
		ll sum = pq.top();
		pq.pop();
		sum += pq.top();
		pq.pop();
		pq.push(sum);
		pq.push(sum);
	}
	ll sum = 0;
	while (!pq.empty()) {
		sum += pq.top();
		pq.pop();
	}
	cout << sum << '\n';
	return 0;
}