[Kotlin] 백준 14698 : 전생했더니 슬라임 연구자였던 건에 대하여(Hard)

문제 링크

14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

---

---

문제 해설

각 테스트 케이스마다 구해야 하는 총 비용은 매 합성 단계마다 필요한 전기 에너지, 즉 매 합성 단계마다 합성되는 슬라임의 에너지들을 모두 곱한 값과 같다. 이 값을 최소로 하기 위해서는 매 합성마다 에너지가 가장 낮은 슬라임 둘을 합성해야 하는데, 예제의 경우를 그림으로 표현하면 다음과 같다.

따라서 우선순위 큐를 사용하면 문제를 수월하게 풀 수 있다. 입력받은 모든 슬라임을 우선순위 큐에 삽입한다. 이후 우선순위 큐에서 슬라임을 2마리 꺼내서 합성을 진행하는데, 최종 슬라임의 에너지가 Long 타입 범위에 포함되는 \(2\times 10^{18}\)이하라는 것이 보장되므로 슬라임을 합성할 때는 나머지 연산을 수행하면 안된다. 슬라임을 합성하면서 나머지 연산을 수행한다면 슬라임의 에너지 순서가 흐트러질 수 있기 때문이다.

 

하지만 슬라임을 합성하는데 드는 총 비용은 Long 타입의 범위를 넘어갈 수 있으므로, 계산할 때마다 나머지 연산을 수행해서 오버플로를 방지해야 한다.

---

Code

import java.util.PriorityQueue
import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val mod = 1_000_000_007
    repeat(readLine().toInt()) {
        val slimes = PriorityQueue<Long>()
        readLine()
        StringTokenizer(readLine()).apply { while (hasMoreTokens()) slimes.add(nextToken().toLong()) }
        var cost = 1L
        while (slimes.size > 1) {
            val slime1 = slimes.poll()
            val slime2 = slimes.poll()
            val newSlime = slime1 * slime2
            slimes.add(newSlime)
            cost *= (slime1 % mod * slime2 % mod) % mod
            cost %= mod
        }
        bw.write("${cost}\n")
    }
    bw.close()
}