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

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

접근법

start를 0으로 설정하고 trees에서 가장 높은 나무를 max()함수로 찾아 end로 설정한다.
for문으로 trees에 있는 나무들을 하나씩 꺼내며 mid값과 비교하며 자른다(cut_tree에 저장).
만약 나무가 M보다 많이 잘렸다면(if cut_tree >= M) mid 값을 키운다.

"""이분탐색"""

from sys import stdin

N, M = map(int, stdin.readline().split())  # N = 나무 수, M = 집으로 가져갈 나무 길이
trees = list(map(int, stdin.readline().split()))

start, end = 0, max(trees)  # 이분탐색용 왼쪽 오른쪽 설정

while start <= end:
    mid = (start+end)//2
    cut_tree = 0  # 잘린 나무 합을 저장하기 위한 변수
    for i in trees:
        if i > mid:  # mid보다 큰 높이의 나무는 잘림
            cut_tree += i - mid

    if cut_tree >= M:  # 원하는 나무 높이보다 더 많이 잘렸다면 start에 mid+1 입력
        start = mid + 1
    else:  # 원하는 나무 높이보다 덜 잘렸다면 end에 mid-1 입력
        end = mid - 1
print(end)

과제

CPython의 경우 시간초과로 실패가 뜬다. 개선하는 방법을 공부해야겠다.