백준 13975번 파일 합치기 3

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

13975번: 파일 합치기 3

문제 설명

백준 11066번 파일 합치기 1 : https://suhwanc.tistory.com/76

와 같은 문제인데, 이 문제는 연속된 두 파일이 아니라 순서를 아무렇게나 해도 상관없다.

 

풀이

priority_queue를 사용하는 최소 힙 문제입니다!

여러 파일을 합쳐 하나로 만들 때 합치는 최소 비용을 구하기 위해선

모든 파일에 대해서 가장 크기가 작은 두 파일들을 계속해서 합쳐주면 된다.

왜냐하면, 크기가 큰 파일을 일찍 합쳐버리면 그 파일은 언젠가 한 번 더 합쳐지기 때문에 최대한 늦추는 게 좋다.

그렇다면 모든 상황에 대해 크기가 작은 두 파일을 구하기 위해서 오름 차순으로 정렬 후 최소 값 두 개를 더하고, 그 결과를 넣고, 다시 정렬하고.. 이런 방법을 사용하지 말고 최소 힙을 사용하면 된다!!

 

최소 힙이란? : 완전 이진트리 기반으로 모든 부모 노드가 자식들의 노드보다 작은 자료구조를 말한다.

다행히 c++에서는 <queue>, <functional> 헤더를 이용해 최소 힙을 구할 수 있다!

 

최소 힙 만드는 방법

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
 
int main(){
    priority_queue<int, vector<int>, greater<int> > pq;
}

 

이렇게 최소 힙을 만들어 주고, 모든 파일들을 최소 힙에 넣은 후,

최소 힙의 루트를 두 번 더하면서 빼고, 다시 넣는 과정을 반복한다.

이때 n개의 파일을 1개로 줄이는 파일 합치기 횟수는 반드시 n-1번 이므로

위 과정을 n-1번 반복한 결과를 출력한다.

 

소스 코드

#include <iostream>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;
 
int main()
{
    int t; scanf("%d", &t);
    while (t--) {
        //최소 힙?
        priority_queue<long long, vector<long long>, greater<long long> >q;
        int k; scanf("%d", &k);
        for (int i = 0; i < k; i++) {
            int temp; scanf("%d", &temp);
            q.push(temp);
        }
        long long ans = 0;
        // 각 파일 합치는 횟수 : k-1번?
        for (int i = 0; i < k - 1; i++) {
            long long temp = 0;
            temp += q.top();
            q.pop();
            temp += q.top();
            q.pop();
            q.push(temp);
            ans += temp;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~