백준 13975 파일 합치기 3

임찬형·2022년 11월 14일
0

문제 팁

목록 보기
70/73

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

각 파일들의 크기가 주어지고, 모든 파일들을 합쳐 하나의 파일로 만든다.

비용은 두 파일을 합칠 때 두 파일의 크기의 합만큼이 추가되며, 파일들을 하나로 만들 때 필요한 최소비용을 구하는 문제이다.

보자마자 알고리즘 강의시간에 배웠던 허프만 코딩이 생각났다.

파일의 개수가 N개이면, 반드시 N-1번을 합치는 작업을 해야 하며 비용은 파일의 합 만큼 추가되므로 그때그때 비용이 최소인 두 파일들을 합쳐야 한다고 생각했다.

이를 구현하기 위해 Priority Queue가 필요하다고 생각했으며, 풀이 알고리즘은 아래와 같다.

  1. Minimum Priority Queue를 준비한다.
  2. 모든 파일들을 PQ에 넣는다.
  3. PQ의 크기가 1이 될 때까지 PQ에서 두 파일을 꺼내 합친 후 합친 크기를 다시 PQ에 넣는 작업을 반복하며 cost에 추가한다.
  4. PQ의 크기가 1이 된 경우의 cost를 정답에 추가한다.
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으로 해야 한다.

0개의 댓글