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

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

2805번: 나무 자르기

 

 

높이의 최댓값을 구하는 이분탐색 문제입니다.

 

mid는 높이의 최댓값입니다. 따라서 tree를 돌면서 mid보다 큰 만큼 자릅니다.

총 자른 길이(count)가 집에 가져가야 하는 숫자(M)보다 많으면 start를 옮기고 정답을 업데이트합니다.

import Foundation

let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = arr[0]
let M = arr[1]
let tree = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted()

var height = 0
var start = 0
var end = tree.max()! // 가장 긴 경우

while start <= end {
    let mid = (start + end) / 2 // 높이의 최댓값
    var count = 0
    
    for t in tree {
        if t > mid {
            count += t - mid //  tree를 돌면서 mid보다 큰 만큼 자릅니다.
        }
    }
    
    if count >= M {
        start = mid + 1
        height = max(height, mid)
    } else {
        end = mid - 1
    }
}

print(height)