[ 백준 / C++ ] 15903 : 카드 합체 놀이

[ 문제 ]

 

15903번: 카드 합체 놀이

 

[ 접근방법 ]

 

우선순위 큐를 활용하여 매번 제일 작은 두 카드를 고르고 합친다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    while(m--){
        ll a = pq.top();
        pq.pop();
        ll b = pq.top();
        pq.pop();

        a += b;

        pq.push(a);
        pq.push(a);
    }

    ll sum = 0;
    while(!pq.empty()){
        sum += pq.top();
        pq.pop();
    }

    cout << sum;

    return 0;
}