(13975) 파일 합치기 3

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

단계별로 풀어보기

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

 

 

 

DP로 풀었던 파일 합치기 문제인데 이웃한 파일끼리만 합칠 수 있다는 조건이 사라졌다. 이 경우 매 단계마다 가장 크기가 작은 두 파일을 합치는 것이 이득이다. 증명은 어렵지만 직관적으로는 이해하기 쉽다.

하프먼 코딩이 이러한 과정으로 이루어진다.

 

 

 

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

long solve(){
  int k;
  
  cin >> k;
  
  priority_queue<long, vector<long>, greater<long>> pq;
  
  for(int i=0;i<k;i++){
    int t;
    
    cin >> t;
    
    pq.push(t);
  }
  
  long cost= 0;
  
  while(pq.size()>1){
    long a= pq.top();
    pq.pop();
    long b= pq.top();
    pq.pop();
    
    cost+= (a+b);
    pq.push(a+b);
  }
  
  return cost;
}

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;
}