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

문제

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

백준 1715

 

문제 내용

정렬된 두 묶음의 숫자카드가 있다. 각 묶음의 카드의 수가 A, B개일 대, 두 묶음을 하나로 합칠 때 A+B번의 비교가 필요하다.

N개의 카드 묶음을 받아, 이들을 두 묶음씩 골라 서로 합쳐나가려고 한다. 

최소 몇 번의 비교가 필요한지 구하면 된다.

 

문제 풀이

문제에 나와있는 대로, 매번 가장 묶음이 작은 것을 2개 골라 합치면 된다.

priority_queue를 통해 이 문제를 해결할 수 있다. (최소힙 사용)

 

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, tmp;
    priority_queue<int, vector<int>, greater<int>> pq;

    cin >> n;
    while (n--) {
        cin >> tmp;
        pq.push(tmp);
    }

    int compare = 0;
    while (pq.size() > 1) {
        int p1 = pq.top();
        pq.pop();
        int p2 = pq.top();
        pq.pop();

        compare += (p1 + p2);
        pq.push(p1 + p2);
    }

    cout << compare;
}