baekjoon 2805: 나무 자르기

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

2805번: 나무 자르기

---

이진탐색을 이용하여 절단기의 높이를 최대로 하는 경우의 절단기높이를 구하는 문제이다.

 

절단기의 높이를 st와 ed의 중간으로 잡은 뒤,

 

원하는 나무 양보다 많이 나오면? ==> st를 더 올려

 

원하는 나무 양보다 적게 나오면? ==> ed를 더 내려

 

위와같은 로직으로 이진탐색을 돌면 풀린다.

n,m = list(map(int,input().split()))
arr = list(map(int,input().split()))
st = 0
ed = arr[-1]

while st+1 < ed:
    height = (st+ed)//2

    tree = 0
    for i in range(len(arr)):
        if (arr[i] - height) >=0:
            tree+= arr[i] - height
    # 나무양이 많이 나오면 st올리기
    if tree >= m :
        st = height
	# 나무양이 적게 나오면 ed내리기
    if tree< m:
        ed = height

print(st)