13975 백준 - 파일 합치기 3, C++, 우선순위 큐

13975번: 파일 합치기 3

#include <iostream>
#include <queue>
using namespace std;

int t;

int main(){
    scanf("%d", &t);
    while (t--){
        long long ans = 0, input;
        int k;
        priority_queue<long long> pq;
        
        scanf("%d", &k);

        for(int i = 0; i < k; i++){
            scanf("%lld", &input);
            pq.push(-input);
        }

        int count = 0;
        while(!pq.empty()){
            if(count == k - 1)
                break;
            
            long long cardA = -pq.top();
            pq.pop();
            long long cardB = -pq.top();
            pq.pop();

            long long newCard = cardA + cardB;
            pq.push(-newCard);
            ans += newCard;
            count++;
        }

        printf("%lld\n", ans);
    }
    
}

---

 첫 줄에서 테스트케이스 수를 입력받은 뒤 테스트 케이스별로 풀이를 하면 되는 문제였습니다. 우선순위 큐를 작은 수가 먼저 나오게 설정한 다음

  1. 우선순위 큐에서 나온거 2개 합치기

  2. 비용은 따로 변수에 저장

  3. 이후 결과물은 다시 큐에 삽입

하면 풀 수 있는 문제였습니다. 코드가 어려운건 아니지만 우선순위 큐에 대한 이해가 필요한 문제였습니다.