[BOJ] Q2805 나무 자르기

[BOJ] Q2805 나무 자르기

Question

Language: Python

Difficulty: Silver 2

해당 문제는 이분 탐색의 대표적인 풀이 유형으로 q1와 유사한 방식으로 문제를 풀이하면 된다.

Solution

def solution():
    start,end=0,1000000000
    max_tree_height=0
    while start<=end:
        mid=(start+end)//2
        remaining_tree=0
        for tree in trees:
            remaining_tree+=max(tree-mid,0)
        
        if remaining_tree>=m:
            max_tree_height=max(max_tree_height,mid)
            start=mid+1
        else:
            end=mid-1
    
    print(max_tree_height)

if __name__ == "__main__":
    n,m=map(int,input().split())
    trees=list(map(int,input().split()))
    solution()