백준 2805 / 나무 자르기

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

이 설명을 보고 푸는 것이 도움이 될 것 같다. 
https://sarah950716.tistory.com/16

def solution(n, m, trees):
    def cut(mid):
        cut_trees = 0
        for tree in trees:
            if (temp := tree - mid) > 0:
                cut_trees += temp
        return cut_trees

    def solve():
        answer, left, right = 0, 0, max(trees)
        while left <= right:
            mid = (left + right) // 2  # 절단기 높이
            cut_trees = cut(mid)  # 자른 나무
            if cut_trees < m:  # 자른 나무가 필요한 나무 보다 작다면
                right = mid - 1  # 절단기 높이를 더 낮춰야 함
            else:  # 자른 나무가 필요한 나무와 같거나 크다면...
                answer = mid
                left = mid + 1
            print(left, mid, right, cut_trees, m, answer)
        return answer

    return solve()


print(solution(4, 7, [20, 15, 10, 17]))
# print(solution(5, 20, [4, 42, 40, 26, 46]))

left, mid, right, cut_trees, m, answer

11 10 20 22 7 10
16 15 20 7 7 15  << 정답을 찾았을 때
                    절단기 높이를 높여(=더 작게 잘랐을 때) 더 좋은 답이 있는 지 확인을 해야한다. 
16 18 17 2 7 15  << mid를 더 높였는 데 답이 아니다. 
16 16 15 5 7 15  << mid를 조금 낮췄는 데 (15보다는 높다) 답이 아니다. 
15