[C++] 백준 13975 - 파일 합치기 3

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

13975번: 파일 합치기 3

 

<알고리즘 분류>

   - 우선순위 큐(Priority Queue)

   - 그리디 알고리즘(Greedy Algorithm)

 

<풀이> 

  1. 처음에는 파스칼의 삼각형을 떠올려, 중간에 있는 값들을 최솟값으로 지정하고, 가장자리로 갈수록 오름차순의 나열을 떠올렸다. 

  하지만 이 과정을 한다고 해도, 덧셈 과정에서 for문을 필연적으로 두 번 사용해야 하기에 O(N^2)의 시간복잡도를 가져 시간초과가   날 것이라는 예상을 했다. 그 해결책으로, 우선순위 큐(Priority Queue)를 떠올렸다.  

 

  2. 이번 13975번 문제에서 우선순위 큐 사용 방법은 이러하다. 자세한 내용은 그림을 참고하길 바란다. 

<주의사항>

  1. 자료형에 주의해야 한다. K는 최대 1,000,000개 이므로, 한 장에 최대 10,000의 입력이 들어가면 int형에서는 오버플로우(overflow)가 일어날 수 있다. 따라서 int 자료형 대신 모두 long long 자료형으로 바꿔줘야 한다. 

 

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>


using namespace std;

int T, K; // T:테스트케이스 개수, K: 장의 개수 

int main(){
    priority_queue <long long, vector<long long>, greater<long long>> chapter;
    cin >> T;
    while(T--){
        cin >> K;
        long long result = 0;
        for (int i=0; i<K; i++){
            int x;
            cin >> x;
            
            chapter.push(x);
        }
        
        while(chapter.size() != 1){
            long long first = chapter.top();
            chapter.pop();
            long long second = chapter.top();
            chapter.push(second+first);
            result+=second + first;
            chapter.pop();
        }

        while(!chapter.empty()) chapter.pop();

        cout << result << "\n";
    
    }

}