2805 통나무 쪼개기/파이썬

나무 자르기 문제.
I : 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

O : 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

ex input:
4 7
20 15 10 17

ex output:
15

ex input2:
5 20
4 42 40 26 46

ex output2:
36

import sys

n, required_logs = map(int, sys.stdin.readline().split())
# 이분 탐색이니 sorted 로 input 받음.
trees = sorted(list(map(int, sys.stdin.readline().split())))

if n == 1:
    print(trees[0] - required_logs)
    exit(0)

# 이분탐색 시작, 끝점 설정.
# start 가 1인 이유는 높이가 1 부터 시작하므로 (최소높이)


# 주의 할 것은 index 로 기준을 나누어 이분탐색을 하는 것이 아니다.
# 높이로 이분탐색을 실시한다.
start = 0
end = trees[-1]
# 추가: 시작점과 끝점 설정은 잘라낼 높이의 (탐색할 대상의) 후보가 될 수있는 지점의 최소 최대를 설정한다고 보면 될 듯.

while start <= end:
    # 중간지점 설정 (인덱스가 아니고 높이의 중간지점임.)
    mid = start + (end - start) // 2
    obtained_logs = 0
    for i in range(n):
        if trees[i] >= mid:
            # 잘라낸 만큼 임시 변수에 저장한다.
            obtained_logs += trees[i] - mid
    # 만약에 해당 높이(mid)로 잘라낸 결과가 필요한 결과보다 작다면,
    if obtained_logs < required_logs:
        end = mid - 1
    # 같거나 더 많이 get 했으면,
    else:
        start = mid + 1
print(end)

# 답이 end 인 이유는, 마지막에 후보가 2개 남았을 때
# 예를 들어 아래의 케이스에서 정답은 5이다.
# 3 7
# 1 6 8

# 이전과정에서 5일때 성립하여 start 를 mid+1 로 밀어준다.
# 5(정답)             6(start) 7 (end) 상황일때,
#               mid 는 6이고, 정답은 5이므로 부족하여 end = mid -1 로 조정된다.