[백준] 2805 - 나무 자르기(Python)

문제 출처:

www.acmicpc.net/problem/2805

2805번: 나무 자르기

문제 풀이:

• 이분탐색 문제이다.
• 아마도 이분 탐색인 문제를 파악하지 못하고 푼다면 시간초과를 마주하게 될 것이다.
• 필자는 아무리 생각해보아도 이분 탐색이 어떻게 적용되는지 모르겠어서 질문 게시판을 참조햇다
  • 자르려는 높이를 x라고 하면, 그 때 잘라내는 나무의 양을 O(N)에 구할 수 있습니다. x가 작을 수록 나무의 양이 같거나 많아지는 것이 자명하므로, 높이 x에서 구한 나무의 양이 M보다 크면 x를 키우고, M보다 작으면 x를 줄이는 방법으로 최대 O(log10억)번의 O(N)개 탐색으로 답을 구할 수 있습니다.
• 이분 탐색으로 찾을 값을 답의 높이라고 생각하면 left와 right가 바뀌는 순간이 최대값이므로 이분탐색으로 해결할 수 있는 것이다.
• 또한 이분 탐색으로  문제를 풀었을때 Python은 시간초과가 난다. pypy3로 제출해야 한다.
• Python으로 푸신 분들의 코드를 보았는데 Counter 라이브러리를 사용하면 통과가 되기는 한다.

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

right=max(h)
left =1

while(left <= right):
    mid = (left+right)//2
    get_trees =0
    for i in h:
        if(i>mid):
            get_trees+=(i-mid)
    if(get_trees>=m):
        left = mid+1
    else:
        right = mid-1

print(right)