[BOJ] 2805 / 나무 자르기 / Python 파이썬

[BOJ] 2805 / 나무 자르기 / Python 파이썬

[BOJ] 2805 / 나무 자르기 / Python 파이썬

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

2805번: 나무 자르기

 

풀이

이진탐색의 기본 문제이다.

 

주어진 나무의 높이들을 빼주면서 결과를 비교하여, 탐색 범위를 좁혀 주는 방식으로 이진탐색을 하였다.

 

• res < M : 자를 높이 감소
• res >= M : 자를 높이 증가

 

N, M = map(int, input().split())

trees = list(map(int, input().split()))

end = max(trees)
start = 1


def cutTree(h):
    global M
    res = 0
    for t in trees:
        if t-h > 0:
            res += (t-h)
    return res


while start <= end:
    mid = (start+end)//2

    res = cutTree(mid)

    if res < M:
        end = mid-1
    else:
        start = mid+1

print(end)