문제

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

나의 코드

"""
1. 아이디어
딱히 아이디어 랄게 없이 이분탐색으로 풀면 되는 문제이다.
대신 마지막 출력할때 mid가 아닌 right를 출력해야 한다.
예시1 에서 mid가 16일때 right는 15로 넘어가면서 반복문이 나오게 된다.

2. 시간복잡도
O(logN)정도?
"""

from sys import stdin
input = stdin.readline

n, m = map(int, input().split()) # 나무 수, 필요한 나무 길이
trees = list(map(int, input().split()))
left, right = 1, max(trees) # 시작점, 끝점

while left <= right:
    mid = (left + right) // 2

    cut_tree = 0 # 잘린 나무의 합
    for tree in trees:
        if tree - mid > 0: # mid보다 큰 나무 높이는 잘림
            cut_tree += (tree - mid)

    if cut_tree >= m: # 원하는 나무 높이보다 더 많이 잘렸으면
        left = mid + 1
    elif cut_tree < m: # 원하는 나무 높이보다 덜 잘렸으면
        right = mid - 1

print(right)

    

느낀점

전형적인 이분탐색 문제