백준 1715번 카드 정렬하기 with cpp

Priority Queue 를 이용한 카드 정렬하기 문제

문제 링크 BAEKJOON Q_1715

카드를 섞는다. 최소한 몇 번의 비교가 필요한지 구하는 프로그램을 작성하시오.
예를 들어 10 , 20 , 40 장의 카드묶음이 있다면 최소한의 비교 횟수는 100 번이다.
(10 + 20) + (10 + 20 + 40) = 100 이기 때문이다.
즉, 카드가 적은 묶음부터 차례로 섞어주어야 한다.
그렇다면 카드의 수를 저장한 후 정렬을 해주고 앞의 두 수를 빼서 더해주고
더해진 수를 다시 저장한 후 정렬을 해주면 된다.
수의 저장과 정렬이 동시에 필요하기에 Priority Queue 를 사용하면 좋다.

priority_queue<int, vector<int>, greater<int>> pq;

이렇게 pq 에 저장과 동시에 정렬을 할 수 있다.

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> pq; // 작은수부터 오름차순으로 자동정렬
int main()
{
    int n, num, sum = 0;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> num;
        pq.push(num);
    }
    
    while(pq.size() > 1)
    {
        int n1, n2;
        n1 = pq.top(), pq.pop();
        n2 = pq.top(), pq.pop();
        sum += (n1 + n2);
        pq.push(n1 + n2);
    }
    
    cout << sum;
    return 0;
}