[백준 / C++] 15903번: 카드 합체 놀이 (그리디, 우선순위 큐)

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

15903번: 카드 합체 놀이

난이도: solved.ac 실버 1

 

알고리즘 분류

그리디 알고리즘, 우선순위 큐

 

접근 방법

점수를 최소로 하기 위해서는 매 선택마다 가장 작은 수를 가진 카드 두 장을 선택해야 한다.

따라서 가장 작은 수가 top에 오도록 하는 우선순위 큐를 이용한다.

 

우선순위 큐에서 가장 작은 수 2개를 뽑아서 합친 후 그 결과를 다시 우선순위 큐에 두 번 넣으면 된다.

 

그리고 주의해야 할 점이 있는데, m의 범위가 15 * n 까지이므로 int 형 범위를 초과할 수 있으므로 우선순위 큐에 넣을 수를 모두 long long 형으로 선언해야 한다는 것이다.

 

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	ll num, a, b, sum, ans = 0;
	priority_queue<ll, vector<ll>, greater<ll>> pq;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> num;
		pq.push(num);
	}
	while (m--) {
		a = pq.top();
		pq.pop();
		b = pq.top();
		pq.pop();
		sum = a + b;
		pq.push(sum);
		pq.push(sum);
	}
	while (!pq.empty()) {
		num = pq.top();
		pq.pop();
		ans += num;
	}
	cout << ans;
}

 

성능

코드 제출 결과