[Baekjoon-Python] 2805 : 나무 자르기

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

접근

나무 높이는 최대 10억이므로 이분 탐색으로 높이를 구해야 한다.
low를 1, high를 N개의 나무 중 최대 길이로 설정한다.
low와 high의 중간 값인 mid로 나무를 잘라서 M보다 크거나 같은지 확인한다.
M미터를 만들 수 있으면 low = mid + 1, 만들 수 없으면 high = mid - 1로 설정한다.
low가 high보다 작거나 같을 때까지 반복한다.
N개의 나무 중 최대 높이를 L이라고 할 때, 시간복잡도는 O(NlogL)

풀이

from sys import stdin
from collections import Counter

_, M = map(int, stdin.readline().split())
trees = Counter(map(int, stdin.readline().split())) # (1)

low = 1
high = max(trees)
while low <= high:
    mid = (low + high) // 2
    cutting_height = sum((i - mid) * cnt for i, cnt in trees.items() if i > mid)

    if cutting_height >= M:
        low = mid + 1
    else:
        high = mid - 1

print(high)