카드 정렬하기

백준 1715번: 카드 정렬하기

아이디어

항상 제일 작은 카드덩이 두개를 합친다. 최소 힙에서 원소 두개씩 꺼내서 합친다음에 다시 힙에 푸쉬해준다. 이걸 힙에 원소가 딱 하나만 남을때까지 반복하면 된다. 반복하면서 카드 두개 합칠때마다 몇 번 비교했는지 센다.

코드

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int x, ans = 0;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x;
        pq.push(x);
    }
    
    while (!(pq.size() == 1)) {
        int card1 = pq.top();
        pq.pop();
        int card2 = pq.top();
        pq.pop();
        ans += card1+card2;
        pq.push(card1+card2);
    }
    cout << ans;
    return 0;
}

여담

C++에서 우선순위 큐는 기본적으로 최대 힙이다. 이걸 최소 힙으로 바꾸려면

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

이렇게 선언해주면 된다!