https://www.acmicpc.net/problem/2805
N, M = map(int, input().split())
tree = list(map(int, input().split()))
def binary_search(target, start, end):
result_max = 0 # 나무 높이의 합이 정확히 M으로 떨어지지 않을 때 최댓값
while start <= end:
result = 0
mid = (start + end) // 2
for i in tree:
if i > mid:
result += i - mid
if result == target:
return mid
elif result > target :
result_max = mid
start = mid + 1
else :
end = mid - 1
return result_max
print(binary_search(M, 0, max(tree)))
나무의 높이의 합은 정확히 M이 되지 않을 수도 있다. 이때, 절단된 나무의 높이의 합이 M보다 크고 절단기에 설정할 수 있는 높이의 최댓값을 위의 코드에서 result > target
일 때 구할 수 있으므로 result_max에 값을 저장해 놓고 반환한다.