[이진 탐색 알고리즘] 나무 자르기 S3

기출 : BOJ #2805

 

일반적인 이진 탐색 문제처럼 다음 두 가지를 먼저 확인해야 한다

 

1. 변경할 값

2. 체크할 함수

 

변경할 값으로는 절단기의 높이를, 체크할 함수로는 잘린 나무의 합산을 설정했다

 

# input
n,m = map(int,input().split())
tree = list(map(int,input().split()))
answer = 0
tree.sort()

# target 이상인 값들의 합을 출력
def check(target, li):
    sum = 0
    for val in li:
        if val>=target:
           sum+=(val-target)
    return sum

# st~en 사이의 값에 대해 탐색
def bs(st, en, target):
    global answer
    if st>en:
        return -1
    mid = (st+en)//2
    if check(mid, tree)>=m:
        answer = mid
        return bs(mid+1,en,m)
    else:
        return bs(st, mid-1, m)

# 1 ~ tree[n-1]    
bs(1,tree[n-1],m)
print(answer)