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

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

[문제 풀이 사이트]

13975번: 파일 합치기 3

[문제 설명]

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.
예를 들어, C1, C2, C3, C4가 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.
소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.

[입력]

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 1,000,000)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

[출력]

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

[입출력 예]

입력	출력
2 4 40 30 30 50 15 1 21 3 4 5 35 5 4 3 5 98 21 14 17 32	300 826

[문제 풀이]

그리디 알고리즘과 관련된 문제이다.

소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때 하나의 파일로 합치는 최소 비용을 구하기 위해 우선 순위 큐(최소 힙)을 사용했다.

알고리즘은 아래와 같다.

1. 각 파일의 크기를 우선 순위 큐(최소 힙)에 넣어준다.
2. 가장 작은 값 2개를 꺼내어서 합치고 합친 결과를 총 비용을 계산하는 변수와 우선 순위 큐에 다시 넣어준다. 꺼낸 2개는 사라진다.
3. 우선 순위 큐의 사이즈가 1이 될 때 까지(파일이 1개가 될 때까지) 2번을 반복한다.

[최종 코드]

[GitHub]

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int TC; cin >> TC;
    for(int i = 0; i < TC; ++i) {
        int K; cin >> K;
        priority_queue<long long, vector<long long>, greater<long long>> min_pq; // 최소힙
        for(int j = 0; j < K; ++j) {
            long long n; cin >> n;
            min_pq.push(n); // 가장 작은 값이 맨위로 오게된다.
        }
        long long ans = 0;
        while(!min_pq.empty()) {
            if(min_pq.size() == 1) {
                break;
            } else {
                long long num1 = min_pq.top();
                min_pq.pop();
                long long num2 = min_pq.top();
                min_pq.pop();
                ans += (num1 + num2);
                min_pq.push(num1 + num2);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}