[백준/C++] 13975번: 파일 합치기 3

문제

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

---

문제 요약

파일 N개의 크기가 각각 주어질 때, 모든 파일들을 1개로 합치기 위한 최소 비용을 출력한다.

 

한 번에 2개의 파일을 1개로 합칠 수 있고, 파일을 합칠 때마다 두 파일의 크기 합만큼 비용이 든다.

---

코드

#include <iostream>
#include <queue>

# define ll long long

using namespace std;

int t;

priority_queue<ll> pq;

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t;

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

        // 모든 파일을 우선 순위 큐에 삽입하여 정렬하기
        for (int i = 0; i < k; i++) {
            int num;

            cin >> num;

            pq.push(-num);
        }

        ll res = 0;

        while (pq.size() != 1) {

            ll num1 = pq.top();
            num1 = -num1;
            pq.pop();

            ll num2 = pq.top();
            num2 = -num2;
            pq.pop();

            res += (num1 + num2);
            pq.push(-(num1 + num2));

        }

        pq.pop();

        cout << res << "\n";

    }

    return 0;
}

---

코드 설명

그리디 알고리즘으로 해결한다.

 

1. 각 파일의 크기를 우선순위 큐에 모두 삽입한다.

 

2. 가장 작은 파일 두 개를 꺼내고, 합치고, 다시 큐에 삽입한다.

+ 합칠 때마다 비용을 계산한다.

 

3.  우선순위 큐에 1개의 파일만 남을 때까지 반복한다.

 

4. 계산한 비용을 출력한다.