[백준/코틀린] 1654번: 랜선 자르기

링크

1654번: 랜선 자르기

풀이

절단할 랜선의 길이를 매개변수로 두고, 만들 수 있는 랜선의 개수가 N개 이상인지 검사합니다.

N개 이상을 만들 수 있는 최대 길이를 m이라 하면,
- m보다 짧을 때는 조건을 만족하고,
- m보다 길 때는 조건을 만족하지 않습니다.

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

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

코드

lateinit var lines: List<Int>

fun check(mid: Long, n: Int): Boolean {
    return n <= lines.sumOf { it / mid }
}

fun main() {
    val (k, n) = readln().split(" ").map { it.toInt() }
    lines = List(k) { readln().toInt() }

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

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

    println(low)
}