[Algorithm] 백준 - 나무 자르기 (이분탐색)

문제 소개

나무를 어떻게 잘라야 하는지 결정해야하는 이진탐색 문제이다. 

 

문제풀이

이 문제를 보고 이진탐색을 바로 생각할 수 있는 이유는 어떠한 값을 넣게 되면 true, false로 나오게 되고, 어떠한 값들의 집합이 오름차순으로 되어있는 것을 볼 수 있다. 예를 들면 [1, 2, 3, 4, 5] 의 경우가 있을 때, 어떠한 로직에 의해서 [True, True, False, False, False] 로 바꿔줄 수 있다면 이진탐색으로 풀수있는 문제이다.

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
let trees = readLine()!.split(separator: " ").map { Int($0)! }

func cut(_ height: Int) -> Bool {
    var get = 0
    
    for tree in trees {
        get += max(tree - height, 0)
    }
    
    if get >= m {
        return true
    } else {
        return false
    }
}

var low = -1
var high = trees.max()!

while low + 1 < high {
    let mid = (low + high) / 2
    
    if cut(mid) {
        low = mid
    } else {
        high = mid
    }
}

print(low)

 

참고

https://www.acmicpc.net/blog/view/109

이진탐색에 대한 가이드(?) 가 나와있다.