[백준 13975번] [그리디] 파일 합치기 3

전형적인 그리디 문제이다.

 

일단, 문제를 보면 최소 비용을 계산하는 문제이므로 직관적으로 큰 것은 나중에 더하고 싶은 느낌이 든다.

이 지점에서 그리디 문제인지 의심해볼 수 있다.

 

Greedy property를 증명하는 것은 생각보다 간단한데

결과적으로 n개의 element를 1개의 element로 만들기 위해서는 n - 1 번의 파일 합치기를 해야한다.

이때, Current status에서 가장 작은 element를 선택하는 것이 partially optimized하면서 globally optimized를 만족하게 된다.

 

이때, 계속해서 최소값을 불러와주는 작업을 거쳐야하므로 우선순위 큐 자료구조를 사용하면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef long long ll;

int main(void){
    fastio;
    int t;
    cin >> t;
    while(t--){
        priority_queue<ll, vector<ll>, greater<ll> > pq;
        int k;
        cin >> k;
        for(int i = 0; i < k; i++){
            ll temp;
            cin >> temp;
            pq.push(temp);
        }

        ll cost = 0;
        
        while(!pq.empty()){
            ll c1 = pq.top(); pq.pop();
            if(!pq.empty()){
                ll c2 = pq.top(); pq.pop();
                cost += c1 + c2;
                pq.push(c1 + c2);
            }
            else{
                break;
            }
        }
        cout << cost << "\n";
    }
    return 0;
}