[백준/BOJ] 13975. 파일 합치기 3 [Gold 4]

13975. 파일 합치기 3

문제출처 : https://www.acmicpc.net/problem/13975

code

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	long long T, K, x, temp = 0, result = 0;
	priority_queue<long long> pq;

	cin >> T;

	while (T--)
	{
		cin >> K;
		result = 0;
		for (int i = 0; i < K; i++)
		{
			cin >> x;
			pq.push(-x);
		}

		while (pq.size() != 1)
		{
			temp = 0;
			temp += pq.top();
			pq.pop();
			temp += pq.top();
			pq.pop();
			pq.push(temp);
			result += temp;
		}
		pq.pop();
		cout << -result << '\n';
	}

	return 0;
}

엊그제 풀었던 카드정렬하기 문제와 동일한 문제였다.
우선순위 큐에다 넣고 가장 작은것끼리 더해서 넣고, 또 가장 작은것끼리 더해서 넣고... 이런알고리즘인데,
나는 그냥 그리디알고리즘처럼 짠거였는데, 이런 알고리즘을 허프만 알고리즘 또는 허프만 부호화라고 한다.

이 문제에서는 정수를 더해서 압축(?)시켰지만, 문자열에서 문자의 개수가 적은 순서대로 리프로잡고 트리를 만들어서 문자가 많은 순서대로 임시 비트를 붙여 메모리를 압축하면, 우리가 흔히 쓰는 파일 압축법이라고 한다.

이런 공부를 하면서 자연스럽게 배워나가는 과정이 너무 즐겁다.