99클럽 코테 스터디 6일차 TIL + 이분탐색

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

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
trees = list(map(int, input().split()))

start = 0
end = max(trees)
answer = 0 # 절단기 높이
while start <= end:
    mid = (start + end) // 2
    total = 0
    for t in trees:
        if t > mid:
            total += t - mid
    
    if total >= m:
        start = mid + 1
        answer = mid
    else:
        end = mid - 1

print(answer)

• m과 n의 범위를 보고 이분탐색을 생각할 수 있다.
• 절단기 높이의 최댓값을 구하는 것이기 때문에 굳이 mid값을 초기화 해줄 필요 없이 end값이 답이 될 수 있다.