[BOJ 2805] 나무 자르기(Python3)

www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

N, M=map(int, input().split())
trees=list(map(int, input().split()))
start=1
end=2000000000
result=0
 
while start<=end:
    mid=(start+end)//2
    total=0
    for tree in trees:
        if tree>mid:
            total+=(tree-mid)
    if total>=M:
        result=max(result,mid)
        start=mid+1
    else:
        end=mid-1
 
print(result)

전형적인 이분탐색 문제

이때 최소값을 0, 최댓값을 트리의 최대 길이로 설정해주어도 ok다. (트리의 최대길이를 넘는 것과 트리의 최대 길이가 절단기가 되었을 때 결괏값은 같다.)

 

mid 높이로 잘랐을 때 길이가 M 이상이면 오른쪽을 탐색, M 미만이면 왼쪽을 탐색한다. 

이때 길이가 M 이상일 때 절단기 값을 result값에 넣어 최대값을 만날 때마다 갱신해준다.