[BOJ] 13975번 : 파일 합치기 3(C++)

문제 링크 : 백준 13975번

[문제 접근]

각 파일을 합칠 때마다 발생하는 비용의 합을 최소로 해야하므로 합칠 때 비용이 가장 적은 것 2개를 반복적으로 합치면 된다.
이 때, 합치는 파일 2개는 삭제하고 합쳐져서 새롭게 탄생한 파일도 기존 파일과 동일하게 비교하여 가장 적은 것 2개를 합쳐야한다.

즉,
1. 기존 파일 중 가장 적은 파일 2개를 합쳐 새로운 파일을 만든다.
2. 합치는데 사용된 파일 2개를 삭제한다.
3. 파일이 2개 이상 남았으면 1번으로 간다.

K가 최대 1,000,000이므로 매번 정렬하여 구하면 시간초과가 발생한다.
퀵 정렬이라 가정 -> O(n logn)
따라서, 최소힙으로 만들어진 우선순위 큐를 사용하면 시간 안에 구할 수 있다.
힙 -> O(logn)

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int t;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);    
    cin >> t;
    while(t--) {
        int k;
        long long ans=0;
        cin >> k;
        priority_queue<long long, vector<long long>, greater<long long> > q;
        for(int i=0 ; i<k ; i++) {
            int a;
            cin >> a;
            q.push(a);
        }
        while(q.size() > 1) {
            long long sum = q.top();
            q.pop();
            sum += q.top();
            q.pop();
            ans += sum;
            q.push(sum);
        }
        cout << ans << "\n";
    }
    return 0;
}