[BOJ 13975 // C++] 파일 합치기 3

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13975번 문제인 파일 합치기 3이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/13975

13975번: 파일 합치기 3

이전에 쓴 measurezero.tistory.com/66 이 문제에서 greedy 알고리즘을 적용한 논리와 같은 논리를 적용할 수 있는 문제이다. 차이점이 있다면 이 문제는 합의 형태로 나타난 문제이고, 저 문제는 곱의 형태로 나타난 문제라는 것이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using std::cin;
using std::cout;
using std::priority_queue;

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int T;cin >> T;
    for (int t = 0;t < T;t++) {
        priority_queue<long long> pq;
        int K; cin >> K;
        for (int i = 0;i < K;i++) {
            int x; cin >> x;
            pq.push(-x);
        }
        long long ans = 0;
        while (pq.size() > 1) {
            long long temp = 0;
            temp -= pq.top(); pq.pop();
            temp -= pq.top(); pq.pop();
            ans += temp;
            pq.push(-temp);
        }
        cout << ans << '\n';
    }
}