백준 15903

백준 15903

이 문제는 n번의 카드가 주어지고, 임의의 x번카드와 y번카드를 골라 둘에 쓰여있는 숫자를 더한 뒤, x번카드와 y번카드 위의 숫자에 덮어 쓴다. 이걸 m번 반복해서 나올 수 있는 n번 카드들에 쓰여있는 숫자들의 합의 최소를 구하는 문제이다.

우선순위 큐를 미니힙으로 만들고, top에 있는 카드 두장을 뽑고, pop한뒤, 그 카드들을 더한 값을 두번 push 해주는 과정을 m번 반복하면 된다.

#include<bits/stdc++.h>
using namespace std;
priority_queue<long long, vector<long long>, greater<>> pq;
int n, m;
int main() {
	cin >> n >> m;

	while (n--) {
		int a;
		cin >> a;	
		pq.push(a);
	}

	while (m--) {

		long long a = pq.top(); pq.pop();
		long long b = pq.top(); pq.pop();

		long long t = a + b;

		pq.push(t); pq.push(t);
	}
	long long ans = 0;
	int sz = pq.size();

	for (int i = 0; i < sz; i++) {
		ans += pq.top(); pq.pop();
	}
	
	cout << ans << '\n';
}

숫자가 최대 백만까지 가능한데, 카드가 최대 1000개임으로 카드들의 합이 int형을 넘어선다. 따라서 long long 으로 잡아줘야 한다. 틀렸을 경우 범위 확인하기!