[Kotlin] 백준 1715 : 카드 정렬하기

문제 링크

1715번: 카드 정렬하기

---

---

문제 해설

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

위 문제와 매우 유사한 문제이다. 차이점이라면 곱셈이 아니라 덧셈이라는 점과 입력의 개수가 다르다는 것 정도 뿐이다.

 

따라서, 같은 방법으로 접근하면 된다. 우선순위 큐에 카드 묶음의 크기를 모두 추가한 후, 가장 작은 크기의 카드 묶음 2개를 뽑아서 합친 후 우선순위 큐에 새로 합쳐진 카드 묶음을 다시 추가하는 과정을 모든 카드 묶음이 하나의 카드 묶음으로 합쳐질 때까지 반복한다. 이 때 필요한 비용은 각 과정에서 합치는 두 카드 묶음의 크기의 합을 모두 더한 값이 된다.

---

Code

import java.util.PriorityQueue

fun main() = with(System.`in`.bufferedReader()) {
    val cards = PriorityQueue<Int>()
    repeat(readLine().toInt()) {
        cards.add(readLine().toInt())
    }
    var sum = 0
    while (cards.size > 1) {
        sum += (cards.poll() + cards.poll()).also { cards.add(it) }
    }
    println(sum)
}