[백준] 2805번: 나무 자르기

문제

나무 높이 리스트가 주어진다. 그리고 상근이가 가져가고자 하는 나무 길이가 주어진다. 나무 리스트에서 나무를 잘라서 가져가게 되는데, 상근이의 절단기에 높이 H를 지정해주면 해당 높이서부터 나무를 자르게 된다.
나무 4개, 가져가고자 하는 높이가 7m일 때 나무리스트가
20 15 10 17
로 주어지면 H를 15로 해 줬을 때 5 0 0 2 m를 잘라서 가져가게 된다.

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

어떻게 풀면 좋을까?

톱의 높이를 나무의 최대 높이로 잡아버리면 당연히 하나도 못 가져간다.
최소 높이로 잡아버려도 과하게 자르게 될 것이다.
최소와 최대높이의 중간쯤에서 탐색을 시작하자. 그리고 이분탐색의 개념을 적용해서 찾아간다.
결국 최선의 수를 찾기 위한 탐색이 계속 되어야 한다.

내가 했던 실수

😭 몫이 아닌 나누기를 해 버렸다.

풀이

# 5 20
n, m = map(int, input().split())
# 4 42 40 26 46
trees = list(map(int, input().split()))
start, end = 1, max(trees) # 1, 46
result = 0

while start <= end:
    mid = (start + end) // 2 # 23
    cutted_tree_sum = 0
    for tree in trees:
        if tree > mid:
            cutted_tree_sum += (tree - mid)
        if cutted_tree_sum > m:
            break
	# cutted_tree_sum = 62
    if cutted_tree_sum >= m:
        start = mid + 1 # 24
        result = mid # 23
    else:
        end = mid - 1

print(result)