1715번 - 카드 정렬하기(c++)

🗒 1715번 문제

📌 priority Queue를 사용해서 오름차순의 큐를 받아라(카드 합체 놀이와 유사) ❗️

💳 카드 합체 놀이하러 가기

  1️⃣ 카드 정렬 하기 문제는 최소한의 비교 횟수를 구하고 있다.

  2️⃣ 최소 비교 횟수를 구하기 위해선 오름차순으로 큐를 정렬해두고 작은 값들부터 비교 횟수를 구해라.

  3️⃣ pop한 두 값을 더해서 sum에 넣고 sum를 queue에 넣는다.

  4️⃣ 그러면 그 전에 더한 비교횟수와 그 다음 비교 횟수가 더해지고 결론적으로 총 비교 횟수가 나온다.

  5️⃣ queue안에 있는 값이 하나밖에 없으면 cnt를 출력 -> 다 더한 sum이 queue에 들어있기에 !!

➰ 코드로 나타낸 1715번 ➰

#include <iostream>
#include <queue>
typedef long long ll;
using namespace std;

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    priority_queue<ll> pq;
    ll num, cnt = 0;
    
    cin >> num;
    
    while(num--) {
        int n;
        cin >> n;
        pq.push(-n);
    }
    
    while(!pq.empty()) {
        if (pq.size() == 1) {
            cout << cnt << endl;
            break;
        }
        else {
            ll first = -pq.top(); pq.pop();
            ll second = -pq.top(); pq.pop();
            ll sum = first + second;
            pq.push(-sum);
            cnt += sum;
        }
    }
    
    return 0;
}