https://www.acmicpc.net/problem/13975

✍️ 첫번째 접근

priority_queue를 쓰는데 기본적으로 최대힙이므로 최소힙으로 변형해서 수록한 파일의 크기를 push한다. 최소힙이기 때문에 pop을 2번하면 현재 가장 작은 값 2개가 나오는데 이를 더한 값을 push하면 된다. 여기서 주의할 점은, 소설을 구성하는 장의 수는 최대 1,000,000이고 파일의 크기는 최대 10,000이므로 int의 범위를 넘어감을 잊지 말자.

#include <bits/stdc++.h>
using namespace std;
int t,n;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while(t--) {
        priority_queue<unsigned long long,vector<unsigned long long>,greater<unsigned long long>> pq;
        unsigned long long sum = 0;
        cin >> n;
        while(n--) {
            int num;
            cin >> num;
            pq.push(num);
        }
        while(pq.size() >= 2) {
            unsigned long long a = pq.top();
            pq.pop();
            unsigned long long b = pq.top();
            pq.pop();
            pq.push(a+b);
            sum += a+b;
        }
        cout << sum << '\n';
    }

    return 0;
}