(28340) K-ary Huffman Encoding

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

단계별로 풀어보기

42단계(그리디 알고리즘 2) 3번째

 

 

 

파일 합치기 3 문제와 같은데, 2진법이 아니라 k진법으로 허프만 코딩을 해야 한다.

n종류의 문자가 있을 때 k진법 허프만 코딩을 하면 k종류의 문자가 하나로 합쳐지고 k-1개가 줄어든다.

따라서 n을 k-1로 나눈 값이 1이 되도록 가상의 0번 사용한 문자를 추가로 넣는다(우선순위 큐에서 size함수로 조절하려면 다른 예외처리가 또 필요해서 이 방법이 제일 간단한 걸로 기억한다).

마지막에 문자열의 길이를 계산하기 위해서는 허프만 코딩으로 압축된 결과를 역추적해야 하므로 압축하는 과정을 기록하고, 재귀로 역추적한다.

 

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<long,int> p;

long solve(){
  int n, k;
  
  cin >> n >> k;
  
  vector<int> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  if(k>2){
    while(n%(k-1)!=1){
      n++;
      v.push_back(0);
    }
  }
  
  priority_queue<p, vector<p>, greater<p>> pq;
  
  vector<vector<int>> huffman;
  
  for(int i=0;i<n;i++)  pq.push({v[i], i});
  
  for(int next=n;;next++){
    long cnt= 0;
    vector<int> list;
    
    while(list.size()<k){
      cnt+= pq.top().first;
      list.push_back(pq.top().second);
      
      pq.pop();
    }
    
    pq.push({cnt, next});
    huffman.push_back(list);
    
    if(pq.size()==1)  break;
  }
  
  long ans= 0;
  
  auto dfs= [&](auto self, int depth, int now) -> long {
    long res= 0;
    
    if(now>n-1){
      for(int next:huffman[now-n]){
        res+= self(self, depth+1, next);
      }
    }else{
      return v[now]*depth;
    }
    
    return res;
  };
  
  return dfs(dfs, 0, pq.top().second);
}

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    cout << solve() << "\n";
  }
  
  return 0;
}