백준 1654번: 랜선 자르기 (Kotlin)

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

1654번: 랜선 자르기

풀이

길이가 제각각인 k개의 랜선을 일정한 크기 단위로 잘라서 n개 이상을 만들어 내려고 할 때, 그 크기 단위의 최대 값을 구하는 문제였다.

 

주어진 k개의 랜선으로 n개를 만들지 못하는 경우는 없다고 했으니까, 최소 1cm씩 잘라내면 항상 n개 이상을 구할 수 있다. 반대로 k = n = 1 이라면, 주어진 랜선 중 가장 긴 길이 만큼 자를 수 있다.

 

랜선의 길이가 21억cm을 넘기 때문에 1cm부터 차례대로 잘라보면 시간 초과가 날 것이다. 특정 크기로 잘라서 나오는 개수와 n을 비교해서 더 길게 잘라볼지, 짧게 잘라야 하는지 결정할 수 있으므로 이진 탐색을 사용할 수 있다.

 

시간 복잡도:  O(log(2^31)) = 약 31

 

구현 방법

1. 랜선을 입력 받는다.
2. 최소 길이(m) = 1, 최대 길이(M) = 가장 긴 랜선(or 2^31 - 1)으로 시작해서, 이진 탐색으로 랜선을 잘라보며 정답을 구한다.
   1. 각 케이블들을 길이 (m + M) / 2로 자른 개수의 합(count)을 구한다
   2. if (count >= n) -> 더 길게 잘라도 n개가 넘는지 확인해본다 -> m = (m + M) / 2 + 1
   3. else -> 너무 길게 잘라서 모자르다 -> M = (m + M) / 2 - 1
   4. 위 과정을 m <= M일 때까지 반복한다.
3. 이진탐색이 끝났을 때, M 값이 답이 된다.

 

코드 1 (구현 방법대로 m <= M일 때까지 탐색하는 방식)

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val k = input[0].toInt()
    val n = input[1].toInt()
    val cables = LongArray(k + 1) // 랜선

    repeat(k) {
        cables[it] = readLine().toLong()
    }

    print(binarySearch(cables, n))
}

fun cutCables(cables: LongArray, divisor: Long): Int {
    var count = 0L

    cables.forEach { cable ->
        count += cable / divisor
    }

    return count.toInt()
}

fun binarySearch(cables: LongArray, minimumCount: Int): Long {
    var answer = 0L
    var lower = 1L
    var upper = Integer.MAX_VALUE.toLong()

    while (lower <= upper) {
        val mid = (lower + upper) / 2  // 이 과정에서 Long 값이 나올 수 있다
        val numberOfCut = cutCables(cables, mid)

        if (numberOfCut < minimumCount) {
            upper = mid - 1
        } else {
            lower = mid + 1
            answer = mid
        }
    }

    return answer
}

 

코드 2 (m < M일 때까지 탐색하는 방식)

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val k = input[0].toInt()
    val n = input[1].toInt()
    val cables = IntArray(k + 1) // 랜선

    repeat(k) {
        cables[it] = readLine().toInt()
    }

    print(binarySearch(cables, n))
}

fun cutCables(cables: IntArray, divisor: Long): Long {
    var count = 0L

    cables.forEach { cable ->
        count += cable / divisor
    }

    return count
}

fun binarySearch(cables: IntArray, minimumCount: Int): Long {
    var answer = 0L
    var lower = 0L
    var upper = Integer.MAX_VALUE.toLong()
    upper += 1 // while(lower < upper) 방식에서는 최초의 upper가 답인 경우를 구할 수 없어서 1을 더해준다
    
    while (lower < upper) {
        val mid = (lower + upper) / 2
        val numberOfCut = cutCables(cables, mid)

        if (numberOfCut < minimumCount) {
            upper = mid
        } else {
            lower = mid + 1
            answer = mid
        }
    }

    return answer
}