(C++) 백준 1715번 - 카드 정렬하기

문제 링크 : https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

풀이

우선순위 큐와 그리디 알고리즘을 사용하여 풀이하였다.

카드 비교 횟수를 최소화하려면 가장 개수가 적은 두 묶음씩 먼저 합치면서 진행하면 된다.

최소 힙을 사용해서 가장 갯수가 적은 묶음 두 개를 합친 후, 다시 이를 최소 힙에 넣고 앞의 과정을 반복하는 방식으로 풀이하였다. 

#include <iostream>
#include <queue>

using namespace std;

int n, total, fst, snd, result;

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

    priority_queue<int, vector<int>, greater<int> > q;
    cin >> n;
    while(n--){
        int x;
        cin >> x;
        q.push(x);
    }
    if(q.size() == 1) cout << 0;
    else if(q.size() == 2){
        total += q.top();
        q.pop();
        total += q.top();
        cout << total;
    } else {   
        while(!q.empty()){
            if(q.size() == 1) break;
            fst = q.top();
            q.pop();
            snd = q.top();
            q.pop();
            total = fst+snd;
            q.push(total);
            result += total;
        }
        cout << result;
    }
}