[이코테2021] 절단기로 떡 자르기 [이진탐색] - Python

# 떡의 개수(n)와 요청한 떡의 길이(m)를 입력
n, m = map(int, input().split())
# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행
result = 0
while(start <= end):
    total = 0
    mid = (start+end)//2
    for x in array:
        # 잘랐을 때 떡의 양 계산
        if x > mid:
            total += x-mid

    # total이 m보다 작다면 적어도 m만큼은 되어야하니까 절단기 높이(mid) 낮추기
    if total < m:
        end = mid-1
    # total이 m보다 크다면 절단기 높이(mid) 높이고 result에 total 삽입
    else:
        result = mid
        start = mid+1

print(result)