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

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

2805번: 나무 자르기

풀이과정

첫 시도는 주어진 나무 중 가장 높은 것을 기준으로 1씩 줄여가며 답을 탐색하였다.

역시, 시간 초과!!

런타임을 줄이기 위해선 탐색 횟수를 줄어야 한다.

때문에 하나씩 줄여가는 것이 아닌 중간 값을 탐색한다.

2번 예시에 따르면 가장 높은 나무는 46 절단기의 높이 최솟값은 0이므로

초기 max = 46 / min = 0

때문에 그에 중간값인 23을 탐색한다.

23으로 나무를 잘랐을 때 값이 M보다 작다면 max에 중간값을 대입하고,

크다면, min에 대입한다.

하지만, M보다 커도 높이가 최댓값이라면, 정답이기 때문에 클 경우엔 변수에 값을 담아 비교하여 최댓값을 찾아준다.

min + 1 == max 가 참이면 탐색을 끝낸다.

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

let ts = readLine()!.split(separator: " ").map { Int($0)! }
var result = 0
var max = ts.max()!
var min = 0
var sum = 0

while true {
  let point = (max + min) % 2 == 0 ? (max + min)/2 : (max + min + 1)/2
  for t in ts {
    if t - point <= 0 { continue }
    sum += t - point
  }
  
  if sum == m {
    print(point)
    break
  }
  
  if sum < m {
    max = point
    sum = 0
  } else if sum > m {
    min = point
    sum = 0
    result = result < point ? point : result
  }
  
  if min + 1 == max {
    print(result)
    break
  }
}