백준 2805번 나무자르기

문제

백준 2805번
https://www.acmicpc.net/problem/2805

문제 이해

• 이분탐색 이용

파이썬 코드

• min_length를 0으로 설정한 이유: 절단기 높이가 0이란 것은 모든 나무를 다 자른다는 의미로, 전체 나무를 다 자를 수 있게 된다.
• max_length를 max(tree)로 설정한 이유: 절단기 높이가 가장 높은 값을 초과하면, 모든 나무가 잘리지 않는다.

import sys
N, M = map(int,input().split())
tree = sorted(list(map(int,sys.stdin.readline().split())))
min_length = 0
max_length = max(tree)
while min_length <= max_length:
    get_sum = 0
    mid_length = (min_length + max_length)//2
    for i in (tree):
        if i > mid_length:
            get_sum += (i - mid_length)
    if get_sum < M:
        max_length = mid_length -1
    else:
        min_length = mid_length +1
print(max_length)