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

문제 링크

2805번: 나무 자르기

---

---

문제 해설

상근이가 M미터 이상의 나무를 가져가면서 가져가는 나무의 양이 최소가 되는, 즉  절단기의 높이 H의 최대값을 구해야 한다. 단순하게 모든 경우를 하나씩 체크할 수도 있겠지만 나무의 최대 높이가 무려 10억이고 최대 나무의 수도 100만이나 되기 때문에 이렇게 하면 1초에 1억회의 계산을 한다고 해도 최대 1000만초(약 116일)라는 엄청난 시간이 걸린다. 따라서 더 효율적인 방법을 찾아야 한다.

 

이 문제는 이진 탐색의 응용으로 해결할 수 있다. 반드시 M미터 이상의 나무를 자를 수 있는 0미터부터 모든 나무를 자를 수 없는 주어진 나무 높이의 최대값 사이에서 이진 탐색을 진행하면 된다. 아래 그림의 예시를 보자.

나무들이 이러한 모양으로 있다면 첫 번째 경우는 다음과 같이 최대 나무의 높이와 0의 중간값으로 자르는 경우를 들 수 있다.

이렇게 나무를 잘라서 가져가는 나무의 총 길이와 M을 비교하면 다음 두 가지로 나눌 수 있다.

나무를 더 적게 잘라야 할 때는 시작값을 잘랐던 높이로 변경하고 그 중간 값으로 다시 잘라본다. 반대로 나무를 더 많이 잘라야 할 때는 끝값을 잘랐던 높이로 변경하고 그 중간 값으로 다시 잘라본다. 이 과정을 시작값 + 1이 끝값보다 크거나 같아질 때까지 반복적으로 수행했을 때 마지막으로 남는 시작값이 H의 최대값이 된다.

 

다만 반복 도중에 잘라낸 나무 길이가 M과 일치한다면 더 이상 체크할 필요가 없기 때문에 즉시 결과를 출력하고 프로그램을 종료한다.

 

주의할 점은 각 나무의 최대 길이가 10억이기 때문에 Int형을 사용하면 오버플로가 발생할 수 있으므로 잘라낸 나무의 길이는 Long형으로 계산한다. (예를 들어, 나무 5개의 길이가 10억이고 5억의 높이에서 나무를 잘라내면 자른 나무 길이의 총합인 25억이 약 21.47억까지만 저장할 수 있는 Int형의 범위를 초과하여 오버플로가 발생한다.)

---

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(' ').map { it.toInt() }
    val st = StringTokenizer(readLine())
    val trees = IntArray(n) { st.nextToken().toInt() }
    var start = 0	// 시작값
    var end = trees.maxOrNull()	// 끝값 = 주어진 나무 중 가장 큰 높이
    while (start + 1 < end!!) {
        var wood = 0L	// 잘라낸 나무의 총 길이
        // 모든 나무를 시작값과 끝값의 중간으로 잘라내서 wood에 추가
        val h = (start + end) / 2
        for (t in trees) {
            if (t >= h) {
                wood += t - h
            }
        }
        // wood가 m과 일치하면 즉시 종료
        if (wood.toInt() == m) {
            println(h)
            return@with
        }

        if (wood > m) start = h
        else end = h
    }

    println(start)
}