[백준][C++] 1715 카드 정렬하기

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

 

 

알고리즘 종류

    - 우선순위 큐

 

 

 

사고 과정

    - 카드의 합이 작은 것부터 합치면 된다.

        * 10 20 40의 카드를 합칠 때에 큰 카드부터 합치기 시작하면 큰 카드의 숫자를 중복해서 합치게 된다.

        예시) (20 + 40) + (60 + 10) = 150이 나온다. 여기서 60은 40과 20의 합이다. 따라서 작은 수부터 더하면 된다.

 

 

 

구현(C++)

#include <iostream>
#include <queue>
 
using namespace std;
 
int n;
int answer = 0; 
 
vector<int> v;
priority_queue<int> pq;
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    int num;
    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();
        
        answer += a + b;
        pq.push(-(a+b));
    }
    
    cout << answer << endl;
}

 

 

 

시행착오