[백준] 2805 (나무 자르기)

#1 개요

#1-1 문제 이해

'나무를 자르는 높이(cuttingHeight)'가 무엇인지를 묻는 문제다. 그리고 cuttingHeight의 범위는 0 ~ 1,000,000,000이다. 따라서, cuttingHeight를 1씩 증가시켜서 일일히 확인하는 방법은 시간 관계상 힘들다.
 
다행인 것은 cuttingHeight가 증가함에 따라, 얻어지는 '목재의 량(woodQuantity)'의 감소한다는 사실이다. cuttingHeight가 감소하면 woodQuantity는 그대로거나 감소한다.
 
cuttingHeight가 index고, woodQuantity는 value인 배열 woods가 있다고 가정하자. 그 배열의 모습은 아래와 같다.
 

#1-2 가상의 배열 'woods'

M이 285라고 가정한다. 그리고 M값을 만족(= M보다 같거나 큼)하는 woodQuantity(value)에 대한 cuttingHeight(index)는 파란색 글씨로 쓰여진 부분이다. 파란색 글씨 중 가장 큰 cuttingHeight는 22다. 따라서 이 경우 정답은 22가 된다.
 
woodQuantity(value) 부분에 나열된 숫자들의 경향을 보면 가상의 배열 'woods'는 중복을 허용하면서 내림차 순으로 정렬된 배열임을 알 수 있다. 따라서, 'woods'에는 중복된 원소 값이 있는 경우의 이진 탐색을 적용할 수 있다.
 

#2 중복된 원소 값이 있는 경우의 이진 탐색

#2-1 베이스 코드

중복된 원소 값이 있는 경우의 이진 탐색 (Binary Search)

위 게시글에 있는 이진 탐색 함수 binarySearchLastIndex(values : Array<Int>, x : Int) : Int를 가져와서 사용한다. 이 binarySearchLastIndex()를 그대로 사용하지는 않고, 변형을 줄 것이다.
 

#2-2 변형 - 내림차순으로 변경

fun binarySearchLastIndex(values: Array<Int>, x: Int): Int {
    var min = 0
    var max = values.size - 1

    while (min < max) {
        val mid = (min + max) / 2 + 1

        // up
        if (values[mid] > x) {
            min = mid + 1

        // equal
        } else if (values[mid] == x) {
            min = mid

        // down
        } else { // values[mid] < x
            max = mid - 1
        }
    }

    if (values[max] == x) {
        return max
    } else {
        return -1
    }
}

#2-1에 있는 함수는 오름차순 배열을 상정하고 만들어졌다. 'woods'는 내림차순 배열이므로 "up"이라는 주석이 쓰인 부분에 있는 부등호의 방향을 바꾼다.
 

#2-3 변형 - 가상의 배열 사용

fun binarySearchLastIndex(/* values: Array<Int>, */ x: Int): Int {
    var min = 0
    var max = treeHeights.max()

    while (min < max) {
        val mid = (min + max) / 2 + 1

        // up
        if (calWoodQuantity(mid) > x) {
            min = mid + 1

        // equal
        } else if (calWoodQuantity(mid) == x) {
            min = mid

        // down
        } else { // calWoodQuantity(mid) < x
            max = mid - 1
        }
    }

    if (calWoodQuantity(max) == x) {
        return max
    } else {
        return -1
    }
}

fun calWoodQuantity(cuttingHeight: Int): Int {
    var woodQuantity = 0

    // 나무 하나하나 잘라서 woodQuantity에 더해주기
    for (i: Int in treeHeights.indices) {
        var temp = treeHeights[i] - cuttingHeight
        if (temp < 0) {
            temp = 0
        }

        woodQuantity += temp
    }

    return woodQuantity
}

나는 진짜로 존재하는 배열을 순회하지 않을 것이다. 가상의 배열 역할을 할 함수 calWoodQuantity(cuttingHeight: Int): Int를 만든다. 그리고 binarySearchLastIndex()를 수정해 이 가상의 배열을 사용하게 만든다.
 

#2-4 변형 - M값이 'woods'에 없는 경우 고려

M값이 285라고 해보자. 그러나, 나무들의 숫자와 자란 양상에 따라 woodQuantity가 285라는 값을 가지지 못할 수도 있다. 그래도 M보다 큰 woodQuantity를 가지는 cuttingHeight의 최댓값을 정답으로 고르면 되므로 이 경우 정답은 19다.
 
#2-1에 있는 함수 binarySearchLastIndex(values : Array<Int>, x : Int) : Int는 이진 탐색을 적용할 배열에서, 검색할 원소의 값 x가 없으면 -1를 반환한다. -1를 반환받으면 문제를 풀 수 없다.
 
하지만 배열 'woods'는 가상의 배열이다. 내 마음대로 함수 calWoodQuantity(cuttingHeight: Int): Int 를 아래와 같이 바꿔버리면 그만이다. 바로 M값을 초과하는 woodQuantity를 모두 M값이라고 생각하는 것이다.
 

fun calWoodQuantity(cuttingHeight: Int): Int {
    var woodQuantity = 0

    // 나무 하나하나 잘라서 woodQuantity에 더해주기
    for (i: Int in treeHeights.indices) {
        var temp = treeHeights[i] - cuttingHeight
        if (temp < 0) {
            temp = 0
        }

        woodQuantity += temp
    }

    return if (woodQuantity > m) {
        m
    } else {
        woodQuantity
    }
}

이 변경 사항을 그림으로 나타내면 아래와 같다.
 

 

#2-5 오버플로우 처리

fun calWoodQuantity(cuttingHeight: Int): Int {
    var woodQuantity: Long = 0

    // 나무 하나하나 잘라서 woodQuantity에 더해주기
    for (i: Int in treeHeights.indices) {
        var temp = treeHeights[i] - cuttingHeight
        if (temp < 0) {
            temp = 0
        }

        woodQuantity += temp
    }

    return if (woodQuantity > m) {
        m
    } else {
        woodQuantity.toInt()
    }
}

변수 woodQuantity는 어느 순간 Int형의 범위를 넘어갈 수도 있다. 따라서 오버플로우가 일어나지 않게 내부 구조를 변경한다. woodQuantity의 데이터 타입을 Long으로, 넉넉하게 만들었다.

woodQuantity의 데이터 타입을 변경하지 않는 방법도 있다. 문제에서 m ≤ 2,000,000,000라는 조건이 있으므로, woodQuantity가 2,000,000,000과 같거나 큰 순간 바로 m을 return하는 것이다.
 

#3 코드 - 코틀린

var n = -1
var m = -1
lateinit var treeHeights: Array<Int>

fun main() {
    val nAndM = readln().split(" ")
    n = nAndM[0].toInt()
    m = nAndM[1].toInt()

    val stringOfTreeHeights = readln().split(" ")
    treeHeights = Array(n) { 0 }
    for (i: Int in 0..<n) {
        treeHeights[i] = stringOfTreeHeights[i].toInt()
    }

    println(binarySearchLastIndex(m))
}

fun binarySearchLastIndex(/* values: Array<Int>, */ x: Int): Int {
    var min = 0
    var max = treeHeights.max()

    while (min < max) {
        val mid = (min + max) / 2 + 1

        // up
        if (calWoodQuantity(mid) > x) {
            min = mid + 1

        // equal
        } else if (calWoodQuantity(mid) == x) {
            min = mid

        // down
        } else { // calWoodQuantity(mid) < x
            max = mid - 1
        }
    }

    if (calWoodQuantity(max) == x) {
        return max
    } else {
        return -1
    }
}

fun calWoodQuantity(cuttingHeight: Int): Int {
    var woodQuantity: Long = 0

    // 나무 하나하나 잘라서 woodQuantity에 더해주기
    for (i: Int in treeHeights.indices) {
        var temp = treeHeights[i] - cuttingHeight
        if (temp < 0) {
            temp = 0
        }

        woodQuantity += temp
    }

    return if (woodQuantity > m) {
        m
    } else {
        woodQuantity.toInt()
    }
}