BOJ 13975 : 파일 합치기 3

• 문제 링크 : boj.kr/13975
• 난이도 : G4
• 태그 : 그리디, 우선순위 큐

13975번: 파일 합치기 3

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        priority_queue<ll> _pq;
        ll ans = 0;
        for(int i = 0; i < n; i++) {
            int input;
            cin >> input;
            _pq.push(-input);
        }
        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;
}

---

풀이

직관적으로는 매 단계마다 가장 작은 두 파일을 합치는 게 최적이다.

 

합치는 과정을 시각화해보면 리프노드의 수가 N이고, 자식이 0 또는 2 이진트리이다. 이 이진트리에서 어떤 노드가 비용에 더해지는 수는 깊이와 같다. 따라서 어떤 깊이가 더 낮은 노드가 깊이가 더 깊은 노드보다 비용이 작다면 둘을 교환하는 것이 이득이다. 이러한 방식으로 교환을 진행하면 결론적으로 최적의 이진트리가 나오게 된다.

 

직관적으로 생각한 최적의 방법과 최적의 이진트리가 같음을 보일 수 있다.