2805. 나무 자르기

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

✔ 유형 : 이분 탐색

✔ 문제 풀이: 리스트 양쪽에 start와 end 피벗을 두고 범위를 좁혀가며 답을 찾는다.

 

 

 

#2850 나무자르기
#이분 탐색
import sys

input=sys.stdin.readline # input함수 바꾸기

N, M = map(int, input().split())
trees = list(map(int, input().split(' ')))


st, en = 0, max(trees) # 최소 최대값!

while st <= en:
    # 중간 값 구하기이
    mid = (st + en) // 2
    
    count = 0
    for tree in trees:
        if tree > mid: #톱날보다 긴 나무들만.
            count += tree - mid  # 톱날h만큼 자른다

    if count >= M: # 구하려는 나무길이보다 크면 더 잘라야하므로
        st = mid+1 # 범위를 오른쪽으로 좁힌다
    else: # 구하려는 나무길이보다 작으면 덜 잘라야하므로
        en = mid-1 # 범위를 왼쪽으로 좁힌다.
    
    

    
print(en)