Binary Search Problems

[백준 2805번] 나무자르기

단순 탐색을 이용한 풀이.
당연히 시간복잡도가 이진탐색보다 커서 시간초과

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
woods = list(map(int,input().split()))
h = max(woods)
while True:
    h -= 1
    l = 0
    for w in woods:
        diff = w - h if w - h >= 0 else 0
        l += diff
    if l == m:
        print(h)
        break

이진 탐색을 이용한 풀이.

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hs = list(map(int,input().split()))
hi = 1
hf = max(hs)
while hi <= hf:
    mid = (hi+hf)//2
    hdiffs = [ h-mid if h>mid else 0 for h in hs ]
    htotal = sum(hdiffs)
    if htotal >= m:
        hi = mid+1
    else:
        hf = mid-1

print(hf)