[Baekjoon 2805 / python / 실버2] 나무 자르기

import sys

n, m = map(int, sys.stdin.readline().split())  # 나무의 수 / 요구 벌목량

tree = list(map(int, sys.stdin.readline().split()))  # 나무 리스트

tree.sort(reverse=True)  # 내림차순 정렬 (큰 나무부터)

result = 0

# 이분 탐색으로 적절한 "높이"를 탐색한다

start = 1    # 최소 높이

end = max(tree)    # 최대 높이

while start <= end:   # start가 end보다 높아지면 탐색을 끝낸다   ->   while문이 끝나면, 반드시 start가 end보다 1 크다

    mid = (start + end) // 2

    cutTree = 0

    for i in tree:    # 높이(mid)를 설정하고 일일이 벌목을 해본다

        if i > mid:    # 나무가 더 높으면 벌목해서 저장한다

            cutTree += i - mid

        else:    # 나무가 같거나 낮다면 어차피 진행해도 벌목 못하니까 break 한다

            break

   

    if cutTree >= m:    # 나무 많으면 줄이기

        start = mid + 1

    else:    # 나무 적으면 늘리기

        end = mid - 1

print(end)

 
이분 탐색 알고리즘이 사용되는 문제이다.
 
나무의 최소 높이1과 나무의 최대 높이max(tree)를 start와 end 값으로 잡은 후 이분탐색을 실시하면 된다.
이분탐색으로 "높이(mid)"를 탐색하고, 각 높이에 대한 나무 벌목량을 계산하여 요구 벌목량보다 높다면 양을 줄이고, 요구 벌목량보다 적다면 양을 늘린다.
 
start를 높이면 높이가 높아져 나무 벌목량이 줄어든다.
end를 낮추면 높이가 낮아져 나무 벌목량이 늘어난다.
 
난 처음에 대체 왜 end가 답을 도출하는지 이해를 못 해서 몇시간동안 붙잡고 있었는데, 내가 이해한 걸 말해주겠다.
이분탐색의 끝까지 가면 결국 mid(높이)값과 start, end는 겹치거나 1차이가 나게 된다.
이 때 while문의 종료 조건은 start가 end보다 높아지는 것이다.
 
end가 줄어들든 start가 높아지든, 결국 start가 end를 역전해야 while문은 끝나게 되므로, (그렇게 종료조건을 걸었으므로)
반복문 종료 직후의 start와 end는,
end | start 순서로 반드시 1차이가 나게 된다.
 
이 상태에서 mid값은 (start + end) // 2 이기 때문에, 몫만 구하고 나머지를 떼는 // 특성상 값이 1 빠지게 된다.
값이 1 차이나는 두 숫자를 더하면 반드시 홀수이고,
홀수를 // 연산으로 나누면 반드시 1이 빠지기 때문에,
항상 start보다 1만큼 적은 end가 답(mid)을 가리키게 된다.
 
ex) end : 22 start : 23 ===>>>  mid : 45 // 2 -> 22   -> end가 mid를 가리킴
ex) end : 21 start : 22 ===>>>  mid : 43 // 2 -> 21   -> end가 mid를 가리킴
ex) end : 16 start : 17 ===>>> mid : 33 // 2 -> 16    -> end가 mid를 가리킴
ex) end : 17 start : 18 ===>>> mid : 35 // 2 -> 17    -> end가 mid를 가리킴
 
end가 왜 답을 도출하는지 이해가 안돼서 하루종일 생각했다.... 제대로 설명된 글도 없고 영상도 없고.
다른 분들은 내 글을 보고 헷갈리지 않고 바로 이해하길 바란다.