[백준/코틀린] 2805번: 나무 자르기

링크

2805번: 나무 자르기

풀이

절단기의 높이를 매개변수로 두고, 가져갈 수 있는 나무의 길이가 M 이상이 되는지 검사합니다.

M 이상을 가져갈 수 있는 절단기의 최대 높이를 h라 하면,
- h보다 낮을 때는 조건을 만족하고,
- h보다 높을 때는 조건을 만족하지 않습니다.

즉, 검증함수가 단조성(Monotonicity)을 가지므로,
매개변수 탐색(Parametric Search)으로 해결할 수 있습니다.

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

코드

lateinit var trees: List<Int>

fun check(mid: Long, k: Int): Boolean {
    return k <= trees.sumOf { maxOf(it - mid, 0) }
}

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    trees = readln().split(" ").map { it.toInt() }

    var low = 0L
    var high = Int.MAX_VALUE + 1L
    while (low + 1 < high) {
        val mid = (low + high) / 2

        if (check(mid, m)) low = mid
        else high = mid
    }

    println(low)
}