코딩테스트/그리디|힙

[그리디] 백준 1715 카드 정렬하기 C++

유(YOO) 2023. 9. 27. 15:01

 

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

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    int x;
    priority_queue<int, vector<int>, greater<>> pq;
    for(int i=0; i<n; i++) {
        cin >> x;
        pq.push(x);
    }

    long long answer = 0;
    while(!pq.empty()) { // 카드 묶음 순서대로 비교X
        if (pq.size() == 1) break;

        int x1 = pq.top();
        pq.pop();

        int x2 = pq.top();
        pq.pop();

        answer += x1 + x2;
        pq.push(x1+x2);
    }

    cout << answer;

    return 0;
}