백준 6195, Huffman Coding
USACO November 2006 Contest gold 1번 문제.
처음에는 이분 탐색으로 접근했다가 틀렸다.
Huffman Coding 에 대한 사전 지식이 없으면 풀기 어렵다.
문제는 조각을 나누는걸로 주어지지만, 거꾸로 생각해서 합친다고 생각해야 풀린다.
가장 크기가 작은 조각 2개를 뽑아서 합치고, 다시 pq 에 넣어주면서 마지막 1개가 남을 때 까지 합친다.
Source Code
// BOJ 6195
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define ll long long
priority_queue<ll, vector<ll>, greater<ll>> pq;
int N;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
for (int i = 0; i < N; ++i) {
ll t;
cin >> t;
pq.emplace(t);
}
ll ans = 0;
while (pq.size() > 1) {
ll s, e;
s = pq.top();
pq.pop();
e = pq.top();
pq.pop();
ans += (s + e);
pq.push(s + e);
}
printf("%lld\n", ans);
return 0;
}