[BOJ 13975 / C++] 파일 합치기 3 (우선순위 큐)

문제링크: https://www.acmicpc.net/problem/13975

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int k;
        cin >> k;

        priority_queue<ll, vector<ll>, greater<ll>> pq;
        for (int i = 0; i < k; i++) {
            int inp;
            cin >> inp;
            pq.push(inp);
        }

        ll cost = 0;
        while (pq.size() >= 2) {
            ll a = pq.top(); pq.pop();
            ll b = pq.top(); pq.pop();

            cost += (a+b);
            pq.push(a+b);
        }
        cout << cost << '\n';
    }
}

 

 

2. 시간복잡도

k = 10^6 이고, 파일 크기는 10^4이므로 int overflow가 발생할 수 있다. 따라서 long long을 사용해야한다. 우선순위 큐의 push, pop은 lgn에 가능하므로 10^6 * 20 < 10^8으로 시간제한 2초 안에 수행가능하다.

 

 

3. 분석

그리디 접근을 해야한다. 가장 작은 파일의 크기부터 합해서 우선순위 큐에 다시 집어 넣는 방식으로 cost를 계산한다. 

허프만 코드 알고리즘과 유사하다.

pq에서 2개씩 뽑아서 다시 계산한 후 집어넣으므로 pq.size >= 2 일 때까지 수행하면 된다.