[Swift][이분탐색] 백준 2805번 (나무 자르기)

요구능력

이분탐색(upperBound)

 

문제풀이

이전에 풀었던 랜선자르기와 문제유형이 완전 동일하다.

가져갈 수 있는 나무의 크기를 구하기위해 sum으로 관리해줬다.

자를 수 없는 나무의 경우 mid(톱의 높이)보다 낮은 나무들이기 때문에 i - mid < 0일 경우 continue로 건너뛰었다.

 

 

후기

카테고리를 모르고있으면 이문제가 이분탐색인지 어떻게알지😂

코드

import Foundation
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}

let maxArr = arr.max()!

var start = 0
var end = maxArr
while start <= end {
    var sum = 0
    let mid = (start + end) / 2
    for i in arr{
        if i - mid < 0{continue}
        sum += (i - mid)
    }
    if sum < m {
        end = mid - 1
    }else{
        start = mid + 1
    }
}
print(start - 1)