[Kotlin] 백준 23757 : 아이들과 선물 상자

문제 링크

23757번: 아이들과 선물 상자

---

문제 해설

우선순위 큐를 이용하면 수월하게 해결할 수 있다. 아이들이 선물을 가져갈 땐 선물이 가장 많이 남아있는 상자에서 가져가게 되는데, 우선순위 큐를 내림차순 정렬하도록 선언하면 우선순위 큐의 가장 앞에 있는 값은 항상 가장 많은 선물이 담긴 개수가 된다. 즉, 아이들이 선물을 가져갈 때마다 우선순위 큐의 가장 앞에 있는 값을 추출하여 아이들이 원하는 선물의 개수만큼 뺀 이후에 다시 삽입하는 과정을 반복하면 된다.

 

문제에서 모든 아이들이 실망하지 않고 선물을 가져갈 수 있는지 여부를 출력해야 한다. 선물이 가장 많이 남아있는 상자에 원하는 것보다 적은 개수의 선물이 들어있다는 것은 우선순위 큐의 가장 앞에 있는 값에서 \(w_i\)를 뺀 값이 0보다 작은 경우이므로, 반복문을 수행할 때마다 이 경우를 검사하면 된다.

Code

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

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(' ').map { it.toInt() }
    val presents = PriorityQueue<Int>(reverseOrder()).apply {
        StringTokenizer(readLine()).apply { repeat(n) { add(nextToken().toInt()) } }
    }
    val children = StringTokenizer(readLine()).run { IntArray(m) { nextToken().toInt() } }
    for (i in children.indices) {
        if (presents.peek() - children[i] < 0) {
            println(0)
            return@with
        }
        presents.add(presents.poll() - children[i])
    }
    println(1)
}