파일 합치기 3

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

13975번: 파일 합치기 3

 

문제 파악하기

K개의 파일을 합쳐서 하나의 소설로 만들 때, 필요한 최소비용을 구하는 문제입니다. 이전 문제와 다른 점은 파일을 합칠 때, 연속하지 않은 파일 2개를 선택할 수 있다는 것입니다. 이전 문제는 항상 연속된 파일 2개를 선택해야 했지만 지금은 파일 2개의 위치가 어디있든 상관없이 하나의 파일로 합칠 수 있습니다. 그렇기에 이 문제는 단순하게 생각할 수 있습니다.

 

문제 해결하기

파일을 합칠 때 필요한 비용은 두 개의 파일의 크기입니다. 이는 전체 비용을 최소로 만들기 위해서는 항상 합쳐지는 2개의 파일의 크기가 작아야한다는 걸 의미합니다. 그렇기에 우리는 모든 파일 중 크기가 가장 작은 2개의 파일을 찾아서 계속 합치면 우리가 원하는 최소비용을 구할 수 있습니다.

 

그렇다면 크기가 가장 작은 2개의 파일은 어떻게 구할 수 있을까요? 바로 우선순위 큐를 사용하면 됩니다. 2개의 값을 우선순위 큐에서 뽑은 다음, 더해주어 다시 큐에 넣어주는 작업을 반복하면 결국 하나의 소설로 완성될 수 있습니다. 그럼 이 알고리즘은 시간 내 작동할 수 있을까요? 정답은 작동할 수 있습니다. 우선순위 큐에서 최솟값을 추출한 다음, 새로운 값을 넣는 과정은 O(logN)의 시간 복잡도를 가집니다. 그리고 우리는 이 과정을 (N-1)번 반복합니다. 따라서, 전체 알고리즘의 시간복잡도는 O(NlogN)가 되며, N이 최대 50,000이기 때문에 2초라는 시간 내 충분히 작동할 수 있습니다.

 

소소코드

#include <stdio.h>
#include <vector>
#include <queue>
#define lint long long int
using namespace std;
 
int T, N, p;
priority_queue< lint, vector<lint>, greater<lint> > pq;
 
lint cnt;
 
int main() {
    scanf("%d", &T);
    while(T--) {
        // init
        cnt = 0;
 
        // input
        scanf("%d", &N);
        for(int i=0;i<N;i++) {
            scanf("%d", &p);
            pq.push(p);
        }
 
        //search
        while(pq.size()>1) {
            lint a = pq.top(); pq.pop();
            lint b = pq.top(); pq.pop();
 
            cnt += a+b;
            pq.push(a+b);
        }
 
        // print
        printf("%lld\n", cnt);
        pq.pop();
    }
}

후기

우선순위 큐를 사용하는 간단한 문제입니다. 우선순위 큐라는 자료구조를 배우고 연습할 때 적절하다고 생각합니다. 알고리즘을 처음 배우는 사람에게 추천합니다.