[C++] BOJ-1715

 

 

문제풀이

---

1. 우선순위 큐에 각각의 카드 묶음의 크기를 집어넣는다.

 

2. 우선순위 큐에 들어있는 카드묶음 중 가장 작은 것들중 2개를 더하고 그 카드묶음을 다시 우선순위 큐에 넣는다.

 

3. 이 과정을 반복하면서 sum에 계속 더해주고 더 이상 비교할 수 있는 카드 묶음이 없다면 sum을 출력한다.

 

 

27분 14초

#include <iostream>
#include <queue>
 
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    priority_queue<int, vector<int>, greater<int> > pq;
    
    int N, num, sum = 0;
    cin >> N;
    
    for(int i = 0; i<N; i++){
        cin >> num;
        pq.push(num);
    }
    
    while(pq.size() > 1){
        
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        sum += a+b;
        pq.push(a+b);
    }
    
    cout << sum;
}