카드 정렬하기 C++ - 백준 1715

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

이 문제는 그리디 문제이다.

카드 정렬 횟수를 최소화 하려면 적은 카드 뭉탱이끼리만 합쳤다가,

최대한 나중에 큰 뭉탱이들을 합치면 된다.

priority_queue(우선순위 큐)를 사용해보았다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
ll ans=0;
int n,ini;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    for(int i=0;i<n;i++){cin >> ini; pq.push(ini);}
    while(pq.size()>1){
        int a=pq.top(); pq.pop();
        int b=pq.top(); pq.pop();
        ans+=a+b;
        pq.push(a+b);
    }
    cout << ans;
    return 0;
}