파이썬 백준 2805번: 나무 자르기

문제

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

2805번: 나무 자르기

 

 

풀이

이진탐색으로 해결 :

start=1, end=나무 길이의 최댓값으로 설정

mid(절단기 높이)를 start와 end의 중간값으로 설정하며 나무 길이 계산 

잘린 나무의 값(result)이 상근이가 가져가려고 하는 나무의 길이(M)보다 크거나 같으면(최댓값을 구해야하기 때문) 절단기 높이 키우기/ 작으면 절단기 높이 줄이기 

import sys
N,M =map(int,sys.stdin.readline().split(' '))
tree_height=list(map(int,sys.stdin.readline().split(' ')))
start=1
end=max(tree_height)
while(start<=end): #이진 탐색
    mid=(start+end)//2
    result=0
    for i in tree_height:
        if i>mid:
            result+=(i-mid)
    if result>=M:
        start=mid+1
    else :
        end=mid-1
print(end)