[BOJ/C++] 1715 카드 정렬하기

우선순위 큐를 이용하여 문제를 해결할 수 있습니다.

작은 묶음의 카드부터 더해나가는 것이 최솟값이기 때문에 오름차순의 우선순위 큐에 모든 카드를 넣습니다.

카드를 2개씩 꺼내어 두 묶음의 합을 우선순위 큐에 삽입하고 누적해서 더합니다.

// boj g4 1715
// 카드 정렬하기
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    int N;
    cin >> N;

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

    for(int i=0; i<N; i++)
    {
        int tmp;
        cin >> tmp;
        pq.push(tmp);
    }
        
    int sum=0;
    while(pq.size()>1)
    {
        int data1=pq.top();
        pq.pop();
        int data2=pq.top();
        pq.pop();
        sum+=data1+data2;
        pq.push(data1+data2);
    }

    cout << sum;

    return 0;
}