[baekjoon] 백준 2805번 (파이썬)

< 문제 >

2805

< SOL >

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
height = list(map(int,input().split()))
start, end = 1, max(height)

while start<=end :

    mid = (start+end) // 2
    need = 0

    for i in height :
        if i >= mid :
            need += i - mid

    if need >= M :
        start = mid + 1

    else:
        end = mid - 1

print(end)

이분 탐색 알고리즘, 제일 작은 값(start)과 제일 큰 값(max) 의 평균을 mid 로 설정 한 다음

평균보다 큰 나무 가지를 잘라 (need += i - mid) , 그 값이 필요값보다 크면 start 를 mid+1, 작으면 end를 mid-1 로 설정하여

위 과정을 반복한다.