2805-나무 자르기

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

2805번: 나무 자르기

계속되는 이분 탐색 시리즈. 이와 비슷한 류의 문제는 같은 방식으로 작성하는 연습을 하고 있다.

나무를 잘라보자

 

      

      

      

    
    

      <python />
    
N, M = map(int, input().split())
trees = list(map(int,input().split()))

lo = 0
hi = max(trees)
mid = (lo+ hi) //2

def is_possible(mid):
    tmp = 0
    for t in trees:
        if t > mid:
            tmp += (t-mid)
    #print(tmp)
    return tmp >= M
ans = 0
while lo <= hi:    
    #print(lo, mid, hi)
    if is_possible(mid):
        lo = mid + 1
        ans = mid
    else:
        hi = mid -1
    mid = (lo+ hi) //2
print(ans)