[백준 2805][Kotlin] 나무 자르기

문제 링크

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

코드

  
fun cutTree(trees: List<Int>, saw: Long): Long {  
    var result: Long = 0  
    for (t in trees) {  
        if (t > saw) {  
            result += (t - saw)  
        }  
    }  
    return result  
}  
  
fun main() {  
    val (n,m) = readln().split(' ').map {it.toLong()}  
    var sum: Long = 0  
    val trees = readln().split(' ').map {  
        val intValue = it.toInt()  
        sum += intValue  
        intValue  
    }  
    var low: Long = 0  
    var high: Long = sum  
    var mid: Long = 0  
    var result = mid  
  
    while (low <= high) {  
        mid = (low + high)/2  
        val value = cutTree(trees, mid)  
        when {  
            (value == m) -> {  
                print(mid)  
                return  
            }  
            (value < m) -> {  
                high = mid - 1  
            }  
            else -> {  
                low = mid + 1  
                result = mid  
            }  
        }  
    }  
    print(result)  
}

설명

자를 수 있는 가장 큰 나무 길이는 주어진 나무 길이의 합(sum)과 같기 때문에 0에서 부터 sum까지 이진탐색을 수행한다.
이진탐색을 한 번 돌 때마다 얻을 수 있는 나무 길이를 비교하여 중간 값(mid)을 산정하며 계산한다.
이때 주의해야할 점은 문제에서 요구하는 것처럼 절단기에서 설정할 수 있는 높이의 최댓값이다. m보다 더 많은 나무를 잘라서까지 필요한 나무를 확보해야한다. 때문에 이진탐색 시 자른 나무 길이(value)가 필요한 나무(m)보다 클 때 result 변수에 대입하여 mid가 m보다 작은 상태로 탐색 종료 시 result를 반환하도록 했다.

후기

알고리즘에는 문제가 없었는데 계속 틀렸던 이유는 오버플로우 때문이었다.
문제 조건에 나무의 길이의 합이 (1백만) X (10억)까지 가능한데 자료형을 Int형으로 계산했었으니 오버플로우가 일어나 정상적인 계산이 되지 않았었다.
Int형의 범위는 약 -21억~21억이므로 문제에서 범위가 나오면 이를 염두해두고 Int와 Long(약 -992경~992경) 중 무엇을 정수 크기로 사용할지 결정하자.