[백준 1715번] [우선순위 큐/ 그리디] 카드 정렬하기

접근 방법

일단, 어차피 카드 묶음이 1개씩 지워지는 상황이므로 무조건 큰 숫자가 나중에 묶이는 것이 유리하다.

그렇지 않으면 반복해서 묶이게 되어 숫자가 더 커지기 때문이다.

 

따라서, 숫자가 작은 것을 먼저 선택하기 위한 자료 구조가 필요하므로 우선순위 큐 자료구조를 활용해주면 된다.

 

코드

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void){
    fastio;
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int> > pq;

    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        pq.push(temp);
    }

    int result = 0;

    while(pq.size() > 1){
        int first = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();
        result += (first + second);
        pq.push(first + second);
    }

    cout << result << "\n";
    return 0;
}