백준 2805번 파이썬 문제풀이(나무 자르기) - 이분탐색

---

간단한 이진탐색 문제입니다. 자를 높이를 반씩 줄여나가면서 탐색하면 쉽게 구할 수 있습니다. 단, 검사할 때 max메서드 쓰면 python3에서 시간초과 납니다. 따라서 pypy3에서 max사용 가능하고 그이외의 경우 if로 비교하셔야 됩니다.

 

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
trees = list(map(int, input().split()))
s = 0
e = max(trees)
ans = 0


def check(mid):
    total = 0
    for i in trees:
        total += max(0, i - mid) #if i - mid > 0 total += i - mid 로 변경(파이썬3로 제출시)

    return total >= M


while s <= e:

    mid = (s + e) // 2
    if check(mid):
        ans = mid
        s = mid + 1
    else:
        e = mid - 1

print(ans)