BOJ 13975번 : 파일 합치기3

합이 최소가 되는 순서는 가장 작은 것 끼리 더하는 방법이다.

따라서 40, 30, 30, 50이 있다면, 가장 작은 30과 30을 먼저 더해야 한다.

이 이후에 가장 작은 것 끼리 더하는 것을 반복하면 되기 때문에 30+30을 다시 배열에 넣고 작은 것 끼리 더하는 것을 반복하면 된다.

즉 

40, 30, 30, 50 -> 30+30 = 60

40, 60, 50 -> 40 + 50 = 90

60, 90 ->  60+90 = 150

이고, 따라서 정답은 60 + 90 + 150 = 300 이다.

한 배열에서 가장 작은 값을 정렬을 따로 하지 않고 추출할 수 있는 방법중 가장 쉬운 것은 우선순위 큐를 사용하는 것이다.

우선순위 큐를 사용할 경우 내부적으로 힙을 사용하여 max 값이 가장 top에 위치하도록 항상 정렬을 해준다.

하지만, 우리는 가장 작은 값을 top으로 해야 하므로, 우선순위 큐에 넣는 값에 -1을 곱해 편하게 사용하였다.

 

또한 정답이 매우 큰 값이므로 long long 자료형을 사용해야 한다.

 

<전체코드>

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
 
using namespace std;
 
typedef long long ll;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int T;
    cin>>T;
 
    for(int t = 0; t<T; t++){
        
        priority_queue<ll> v;
        int n;
        ll ans = 0;
        
        cin>>n;
        for(int i = 0; i<n; i++){
            int tem;
            cin>>tem;
            v.push(tem*-1);
        }
        
        while(v.size()!=1){
            ll a = v.top();
            v.pop();
            ll b = v.top();
            v.pop();
            ans += (a+b);
            v.push(a+b);
        }
        cout<<ans*-1<<endl;
    }
}