[BOJ] 랜선 자르기 in Python & Kotlin

문제풀러 가기!

요새 이분 탐색 문제를 조금씩 풀고 있는데, 쉬운 문제였지만, 감을 계속 맞춰서 가고 있는 것 같습니다.

이분 탐색에서 가장 중요하다고 생각하는 것은 도대체 무엇을 탐색해야 하는가? 라고 생각이 들기 때문에 문제의 가장 마지막에 주어진 글을 자세히 읽어봐야 했습니다. 그래도 빠르게 문제를 풀 수 있어서 정말 다행이네요.

여튼 아이디어는 문제에서 제공한 분할한 랜선 개수를 힌트로 가장 짧은 랜선 분할 길이를 찾는 것이므로

최소: 1
최대: 문제에서 준 최대 길이

로 하여 2분 탐색을 진행하면 되겠습니다.

아래는 풀이들입니다. 오늘은 캡춰가 아닌 풀 코드를 올리겠습니다.

참고 : Kotlin 또는 java의 경우 k값이 2^31-1까지 가기 때문에 Long형으로 받아야 됩니다.

또한 이로 인해 toInt(), toLong() 함수를 많이 사용해야 합니다. Kotlin 또는 Java 주 언어 풀이분들은 주의하셔서 접근하시는게 좋을 것 같습니다.

아래는 파이썬 코드입니다.

import sys
input = sys.stdin.readline

k, n = map(int, input().split())
ren_line = []

for _ in range(k):
    ren_line.append(int(input()))

left, right = 1, max(ren_line)

while left <= right:
    mid = (left + right) // 2
    cnt = 0
    for i in range(k):
        cnt += ren_line[i] // mid
    
    if cnt < n:
        right = mid - 1
    else:
        left = mid + 1

if left == 1:
    print(left)
else:
    print(left-1)

아래는 Kotlin 코드입니다.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (k, n) = readLine().split(" ").map { it.toLong() }
    val arrInt = LongArray(k.toInt()) {0}

    for (i in 0 until k) arrInt[i.toInt()] = readLine().toLong()

    var left: Long = 1
    var right = arrInt.maxOrNull()!!
    var mid: Long
    var count: Long

    while (left <= right) {

        mid = (left + right) / 2
        count = 0

        for (i in 0 until k) count += (arrInt[i.toInt()] / mid)

        when {
            count < n -> {
                right = mid - 1
            }
            else -> {
                left = mid + 1
            }
        }
    }

    when (left) {
        1.toLong() -> println("$left")
        else -> println("${left - 1}")
    }
}