[백준] 2805번: 나무 자르기 (파이썬)

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

 

백준에서 처음 풀어보는 이진탐색 유형 문제이다.

입력 범위가 2억이 넘어서 이걸 어떻게 푸는 거지? 라고 생각하고 문제 유형을 봤는데, 이진 탐색이어서 당황했다.

다음부터 이렇게 입력 범위가 말도 안되게 크면 이진탐색이 생각 날 것 같다.

유튜브에서 동빈나님의 이진탐색 영상을 봤는데, 이 문제 그대로인 문제가 예제로 나왔다. 그정도로 이진탐색의 대표적인 문제인가 보다. 

n,m = map(int,input().split()) #나무의 개수, m: 나무의 길이
arr = list(map(int,input().split())) #각 나무의 길이 입력
arr.sort()
start = 0
end = max(arr)

while (start <= end):
    mid = (start+end)//2
    total = 0
    for x in arr: #하나씩 다 짤라보기
        if x > mid:
            total += x-mid
    
    if total < m: #나무의 길이가 부족할 때 (왼쪽 부분 탐색)
        end = mid - 1
    else: #나무의 길이가 충분할 때 덜 자르기 (오른쪽 부분 탐색)
        result = mid #최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1

print(result)