BOJ/백준 - 1715 카드 정렬하기 C++

작은 수부터 정렬해서 차례로 더해주면 된다.

 

우선순위 큐만 알면 쉽게 풀 수 있는 문제였다.

예제를 보면 N이 3, 차례로 10, 20, 40이 입력되는데

 

1. 10+20 한번, 30+40으로 N-1번 연산해주면 된다. 따라서 pq.size()!=1일때까지 while문을 돌려준다.

2. a와 b를 꺼내서 더해주고, 다시 pq에 push해준다.

3. greater(오름차순)정렬했으므로 작은 것 부터 차례로 더해줄 수 있게 된다.

 

 

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;
 
int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    priority_queue<int> pq;
 
    int N;
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        pq.push(-tmp);
    }
 
    int result = 0;
    while (pq.size()!=1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        result += -(a + b);
        pq.push(a + b);
    }
 
    cout << result;
 
    return 0;
}