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

13975번: 파일 합치기 3

 

문제

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

13975번: 파일 합치기 3

 

 

풀이

두 개의 파일을 합치는데 드는 비용은 두 파일의 크기의 합이다. 합친 파일을 다른 파일과 또 합칠 수 있고 하나의 파일을 만들기 위해 필요한 비용의 최솟값을 구하는 문제다. 각 파일의 크기가 최대 10,000이고 파일의 수가 최대 1,000,000 이므로 long long 자료형을 사용해야 한다.

 

작은 두 파일을 합치면 비용이 적게 들고 그 파일을 합칠 때의 비용도 적게 들 것이라고 생각했다. 따라서 최소 힙을 사용해서 풀기로 했다. 최소 힙을 사용하기 위해 우선순위 큐를 사용했다. 우선순위 큐는 기본적으로 최대 힙이기 때문에 값을 넣고 뺄 때 (-)를 붙여 최소 힙과 같게 사용했다.

 

우선순위 큐의 top 원소(음수)를 꺼내오고 pop 하는 과정을 두 번 반복하고 두 원소의 합(음수)을 정답에 빼준 후 다시 우선순위 큐에 넣어준다. 정답에서 빼는 이유는 두 음수의 합은 음수이기 때문에 양수가 되도록 하기 위해서다. (사실 원소를 꺼내고 넣을 때 -를 붙이고 정답에는 더해줘도 되고, 음수를 꺼내와도 그냥 더해준 다음 출력할 때 -를 붙여줘도 된다.) 이 과정을 우선순위 큐에 원소가 1개 남을 때까지 반복한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    priority_queue<ll> pq;
    int n, x;
    ll ans = 0;
    cin >> n;
    while (n--) {
      cin >> x;
      pq.push(-x);
    }
    while (pq.size() != 1) {
      ll a = pq.top();
      pq.pop();
      ll b = pq.top();
      pq.pop();
      ans -= a + b;
      pq.push(a + b);
    }
    cout << ans << '\n';
  }
  return 0;
}