[BOJ/백준][Gold4] 13975 : 파일 합치기 3 (C++)

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

13975번: 파일 합치기 3

 

 

[난이도] Gold4
[유형] 우선순위큐

[풀이]
https://www.acmicpc.net/problem/11066 문제와 다른점은
꼭 연속된 파일을 합칠 필요가 없이 아무 파일이나 두개를 골라서 합쳐도 된다는 것입니다.

우선순위큐에 모든 파일의 크기를 넣어놓고 작은 것부터 꺼내서 합친 뒤, 다시 넣고를 반복하다
최종적으로 남게되는 1개의 파일의 크기가 최종 정답입니다.

 

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
using ll = long long;
int T,K;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&K);
        priority_queue<ll,vector<ll>,greater<ll>> pq;
        for(int i=0;i<K;i++) {
            int v;
            scanf("%d",&v);
            pq.push(v);
        }
        ll ans=0;
        while(pq.size()>1){
            ll a = pq.top(); pq.pop();
            ll b = pq.top(); pq.pop();
            pq.push(a+b);
            ans+=a+b;
        }
        printf("%lld\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13975.cpp