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

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

2805번: 나무 자르기

 

난이도 : 실버 2
태그 : 이분 탐색, 매개 변수 탐색

 

 

설명

절단기를 H 높이로 했을 때, 그 위의 나무는 모두 잘립니다.

꼭 필요한 만큼의 나무만 가져가되, 적어도 M미터의 나무를 집에 가져가고 싶을 때, 절단기의 높이의 최댓값을 구하는 문제입니다.

 

이진 탐색(이분 탐색)을 응용할 수 있겠는데,

이진 탐색에 기반한 매개 변수 탐색(Parametric Search)를 사용할 수 있을 것 같습니다.

 

이진 탐색은 원하는 값의 인덱스를 찾기 위해 주로 사용됩니다.

매개 변수 탐색은, 이러한 이진 탐색에서 인덱스 대신 특정 값을 찾기 위해 사용하는데요.

쉽게 말해, 인덱스 대신 전기톱의 높이를 찾기 위해 탐색한다고 생각하면 됩니다.

 

 

해당 문제의 예제 하나를 갖고 오겠습니다.

각각 높이가 20, 15, 10 17인 총 4개의 나무가 있습니다.

전기톱의 높이의 최솟값을 0, 최댓값을 나무의 최대 크기인 20으로 잡아보겠습니다.

탐색 1 : low - 0, high  - 20, mid = 10

이진 탐색을 통해 탐색을 하게 될 경우, 전기톱의 높이는 (20 + 0) / 2 = 10 입니다.

전기톱의 높이를 10으로 설정했을 경우, 나무를 각각 10, 5, 0, 7 만큼, 총 22만큼 얻을 수 있습니다.

이는 상근이가 필요한 나무 길이인 7보다 큽니다.

low를 mid + 1 만큼 설정해 또 다시 이진 탐색을 진행할 수 있겠습니다.

 

탐색 2 : low - 11, high  - 20, mid = 15

15로 전기톱을 가동시키면 5, 0, 0, 2로, 총 7 만큼의 나무를 얻을 수 있겠습니다.

전 while을 사용해 이진탐색을 구현하였고, 조건식을 min<=max로 잡았기에

해당 조건문을 만족할 때 까지 계속 while이 돌긴 하겠지만,

최종적으로 위와 같은 과정을 반복해 이진 탐색을 진행하여 최적의 값을 찾을 수 있습니다.

 

 

 

소스코드

fun main() = with(System.`in`.bufferedReader()) {
    val nm = readLine().split(" ")
    val need = nm[1].toLong()

    val trees = readLine().split(" ").map { it.toLong() }.toLongArray()

    var min = 0L
    var max = trees.maxOrNull()!!

    while (min <= max) {
        val mid = (min + max) / 2
        val get = meter(trees, mid)

        if (get >= need) {
            min = mid + 1
        } else {
            max = mid - 1
        }
    }

    print(max)
}

fun meter(arr: LongArray, h: Long): Long {
    var result = 0L
    arr.forEach {
        if (it > h) result += it - h
    }
    return result
}

 

 

 

후기

코딩테스트에서 이진탐색이 나온다면,

보통 이진 탐색 자체가 나온다기 보단 이진 탐색 + 매개 변수 탐색이 주로 나오는 것 같습니다.

해당 문제는 매개 변수 탐색 연습에 아주 좋은 문제 같네요.