[백준] 15903 카드 합체 놀이

그리디 문제이다. 우선순위 큐를 이용해 쉽게 풀 수 있다

최소값 2개를 계속 더해가면 된다

이 때 pq는 최대값을 저장하므로 -를 붙여서 저장해 최소값을 계속 찾아주자

 

소스코드

#include <iostream>
#include <queue>
using namespace std;
#define ll long long
int n,m;
priority_queue<ll> pq;
 
int main(){
    //freopen("input.txt","r",stdin);
    scanf(" %d %d",&n,&m);
    for(int i=0;i<n;i++){
        ll x; scanf(" %lld",&x);
        pq.push(-x);
    }
    while(m--){
        ll a = -pq.top();
        pq.pop();
        ll b = -pq.top();
        pq.pop();
        pq.push(-(a+b));
        pq.push(-(a+b));
    }
    ll ans=0;
    while(!pq.empty()){
        ans+=-pq.top();pq.pop();
    }
    printf("%lld\n",ans);
}