https://www.acmicpc.net/problem/13975
각 파일들의 크기가 주어지고, 모든 파일들을 합쳐 하나의 파일로 만든다.
비용은 두 파일을 합칠 때 두 파일의 크기의 합만큼이 추가되며, 파일들을 하나로 만들 때 필요한 최소비용을 구하는 문제이다.
보자마자 알고리즘 강의시간에 배웠던 허프만 코딩이 생각났다.
파일의 개수가 N개이면, 반드시 N-1번을 합치는 작업을 해야 하며 비용은 파일의 합 만큼 추가되므로 그때그때 비용이 최소인 두 파일들을 합쳐야 한다고 생각했다.
이를 구현하기 위해 Priority Queue가 필요하다고 생각했으며, 풀이 알고리즘은 아래와 같다.
import java.util.*
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val T = readLine().toInt()
val pq = PriorityQueue<Long>()
val answer = StringBuilder()
for(i in 1..T){
pq.clear()
val K = readLine().toInt()
val files = readLine().split(' ').map{it.toLong()}
pq.addAll(files)
var cost = 0L
while(pq.size > 1){
val min1 = pq.poll()
val min2 = pq.poll()
pq.offer(min1 + min2)
cost += min1 + min2
}
answer.append("$cost\n")
}
print(answer.toString().trim())
}
조심해야 할 점은 파일 개수인 K가 최대 1,000,000이고 각 파일의 크기가 최대 9999이므로 값을 합할 때마다 추가되는 cost와 합한 값이 쌓여 들어가는 PQ의 숫자 타입을 Long으로 해야 한다.