[백준] 1654번: 랜선 자르기 - 코틀린(kotlin)

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

문제 해석

기존에 랜선을 K개 가지고 있습니다.

필요한 랜선의 개수 N개가 주어지고 랜선을 잘라서 N개 이상을 만드려고 합니다.

이때 길이를 최대로 만들면서 N개 이상을 만족하는 길이를 구하면 됩니다.

 

가장 단순한 건 2중 반복문이지만 그렇게 되면 백억의 시간 복잡도 이므로 이분 탐색을 통해 답을 찾아가야 합니다.

 

나무 자르기 문제와 매우 비슷한 문제 같습니다.

 

코드

fun main() {
    val (hasLanLineCount, needLanLineCount) = readLine()!!.split(" ").map { it.toInt() }
    val lanLines = IntArray(hasLanLineCount)
    var index = 0
    repeat(hasLanLineCount) {
        lanLines[index++] = readLine()!!.toInt()
    }

    var min = 0L
    var max = lanLines.maxOrNull()!!.toLong()
    var answer = 0L
    while (min <= max) {
        val middle = (min + max) / 2
        var afterDivideLenCount = 0L

        lanLines.forEach { afterDivideLenCount += (it / middle) }

        if (afterDivideLenCount >= needLanLineCount) {
            answer = middle
            min = middle + 1
        } else {
            max = middle - 1
        }
    }
    println(answer)
}

또한 이렇게 범위가 0~2^31-1으로 주어지는 문제는 웬만하면 모두 Long으로 사용하려고 합니다.