[2805] 나무 자르기 in python

 

>> 이분 탐색

>> 정렬

 

 

처음에는 left, right의 값은 인덱스 값이 아닌

현재 톱날의 높이에 기준을 맞춰 지정해주어야 한다.

 

 

 

sorted를 하고 array[n-1]로 최댓값을 구하는 것보다

max(array)로 하는게

실행속도를 더 빠르게 한다!

 

 

n, m = map(int, input().split())
array = list(map(int, input().split()))
left = 0
right = max(array) 
while left <= right:
    mid = (left + right) // 2 # 현재 톱날의 높이
    temp = 0
    for i in array:
        if mid <= i: # 톱날의 높이보다 나무가 높으면 잘라야함.
            temp += i - mid
    if temp >= m: # 자른 나무의 총 길이가 m보다 크거나 같다면?
		# 톱날의 높이가 올라가야 자른 나무의 총 길이가 줄어듬.
		# 톱날의 높이 + 1
        left = mid + 1
    else:
    	# 톱날의 높이가 낮아져야 자른 나무의 총 길이가 늘어남.
        right = mid - 1
print(right)