[백준] 2805 (실버2)

최대와 최소 사이에서 필요한 값을 찾는 문제이다.
범위가 주어져있기 때문에 이분 탐색을 활용하면 문제를 굉장히 빠르게 풀 수 있다.

# binary search
def main():
    n, m = map(int, input().split())

    trees = list(map(int, input().split()))

    start = 1
    end = max(trees)

    print(binary_search(trees, m, start, end))


def binary_search(trees, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        mod = 0
        for tree in trees:
            if tree > mid:
                mod += tree - mid   # 자른 나머지
        if mod >= target:
            start = mid + 1
        elif mod < target:
            end = mid - 1
    return end  # 왜 mid 값이 아니고, end 값인 거지?


main()