木を切る

白駿2805

方法重複文によるバイナリ・ナビゲーション

n, h = map(int, input().split())
# 한 줄에 여러개 받기
tree = list(map(int, input().split()))

# 자를 수 있는 나무 길이의 범위
start = 0
end = max(tree)

while(start <= end):
    
    mid = (start + end)//2 #이진탐색을 위해 반으로 쪼개기
    sum = 0
    for ele in tree:
        if ele > mid : 
            sum += ele-mid #그때그때 mid길이만큼 나무를 잘라 남은 길이의 합을 구하기
    if sum >= h: #최소 h만큼은 잘라야하기 때문에 합이 h보다 크거나 같으면
        max_h = mid #그때의 mid를 기억해준다.(반복문은 조건이 맞는 동안 계속 돌것이므로 알아서 최종 mid의 최댓값이 저장)
        start = mid + 1 #sum이 너무 크면 더 많이 잘라야하기때문에 자를 수 있는 최소 길이를 높여준다.
    elif sum < h: #sum이 너무 작으면 너무 많이 자른것이므로 자를 수 있는 최대 길이를 낮춰준다.
        end = mid - 1
print(max_h) #최대로 자를 수 있는 길이를 출력한다.

バイナリナビゲーション