[ 백준 28340 ] K-ary Huffman Encoding

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

 

 

[ 문제 요약 ]

각 문자의 빈도수인 N개의 정수가 주어질 때 K진법의 허프만 코드로 나타낼 때 주어진 문자열의 가능한 최소 K진법 인코딩 길이를 출력한다.

 

 

[ 문제 풀이 ]

1. 최소 길이를 출력해야 하기 때문에 가장 아래에 가장 적은 수가 들어가야 한다.

2. 이후에는 모두 K만큼 들어간다.

3. N - K + 1을 반복하다가 K보다 작아지는 지점에서의 수가 바로 가장 밑 트리에 들어갈 노드의 수가 된다.

4. 가장 아래에 들어가는 수를 제외하고 나선 모두 K만큼 노드가 들어가면 된다.

 

 

[ 소스 코드 ]

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

long long N, K, t, num, ans, sum;

int main() {
    cin >> t;
    while (t--) {
        cin >> N >> K;
        priority_queue<long long, vector<long long>, greater<long long>> pq;
        for (int i=0; i<N; i++) {
            cin >> num;
            pq.push(num);
        }

        int cnt = N;
        while (cnt > K){
            cnt = cnt - K + 1;
        }

        ans = 0; sum = 0;
        for (int i=0; i<cnt; i++){
            sum = sum + pq.top();
            pq.pop();
        }
        ans = ans + sum;
        pq.push(sum);

        while (pq.size() > 1) {
            sum = 0;
            for (int i=0; i<K && !pq.empty(); i++) { 
                sum = sum + pq.top();
                pq.pop();
            }
            ans = ans + sum;
            pq.push(sum);
        }
        
        cout << ans <<"\n";
    }
}

 

 

 

[ 주의할 점 ]

K진법이므로 일반적으로 2진법의 허프만 코드랑 다르게 가장 아래에 가장 적게 들어가지 않으면 최소 길이가 되지 않는다.