[Boj] 나무자르기 2805(python)

문제링크 : https://www.acmicpc.net/problem/2805

이진탐색 연습문제이며, 먼저 입력된 나무들을 정렬한다.

start를 0으로 end를 max(trees)로 설정한다(필자는 시간복잡도 고려해서 tree[-1]을 사용)

이진 탐색을 하되, 조금 더 최적화하기 위해서 bisect_left(trees, mid)를 사용함

bisect_left(array, value)는 정렬된 순서를 유지하면서 array에 value를 삽일할 가장 왼쪽의 인덱스를 반환한다. 이를 통해, 좀 더 시간을 줄일 수 있다.

from bisect import bisect_left

N, M = map(int, input().split())
trees = list(map(int, input().split()))


trees.sort()
end = trees[-1]
start = 0

while start <= end:
    result = 0
    if start > end:
        break
    mid = (start + end) // 2

    for tree in trees[bisect_left(trees, mid):]:
        if tree > mid:
            result += tree - mid

    if result < M:
        end = mid - 1
    else:
        answer = mid
        start = mid + 1

print(answer)