[Swift 백준] 나무 자르기

 

풀이 아이디어

이분 탐색 문제입니다. 

이분 탐색은 left와 right 의 중간값을 이용해 빠르게 값을 대치하며 찾는 방식입니다.

 

주의할점 

• 톱날의 높이가 나무의 높이보다 높아져도 음수가 되진않는다
• left는 0 부터 시작 right는 나무 중 가장 큰 값이다 ( 나무를 가져가지 못하는 경우는 없으니, 전체 다 가져가야하거나 목표치가 0 일수 있음)

 

풀이

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)! }

var left = 0
var right = trees.max()!
var h = 0

while left <= right {
    // 사실상 현재 톱날의 높이임
    let mid = (left + right) / 2
    
    // mid 값을 빼도 음수가 되지 않아야한다
    let wood = trees.reduce(0) { $0 + max(0, $1 - mid) }
    
    if wood >= m {
        // 가져갈 수 있는 나무가 충분하면 높이를 더 올릴 수 있음
        h = mid
        left = mid + 1
    } else {
        // 가져갈 나무가 부족하면 높이를 낮춰야 함
        right = mid - 1
    }
}

print(h)