[백준 1715번] 카드 정렬하기

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

1715번: 카드 정렬하기

<문제 풀이> 우선순위 큐

항상 카드 수가 최소가 되는 카드 묶음끼리 뭉치면 됩니다.

최소 힙을 사용해서 입력받은 데이터를 모두 push 합니다.

 

사이즈가 1이 될 때까지 다음을 반복합니다.

1. 최소 힙에서 두 개를 꺼낸다.

2. 두 개를 더한 결과를 cnt에 추가한다.

3. 두 개를 더한 결과를 최소 힙에 push 한다.

 

<C++ 소스 코드>

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int> > pq;
    while (n--) {
        int num;
        cin >> num;
        pq.push(num);
    }
    int cnt = 0;
    while (pq.size() != 1) {
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        cnt += a + b;
        pq.push(a + b);
    }
    cout << cnt;
 
    return 0;
}