2805번: 나무 자르기 [Python]

일단 되게는 하자

n, m = map(int, input().split())
v = sorted(list(map(int, input().split())))
p = n - 1
sum = 0

if len(v) > 1:
    for i in range(1, n):
        sum += (v[p] - v[p - 1]) * i
        if sum >= m:
            print(v[p - 1] + (sum - m) // i)
            break
        p -= 1
    if sum == 0:    # 예외1. 모든 수가 같은 경우
        print(v[p] - m // n)
    elif sum < m:   # 예외2. sum이 m 보다 낮을 경우
        tmp = (m - sum) // n
        if (m - sum) % n > 0:   # 올림
            tmp += 1
        print(v[p] - tmp)
elif v[p] == 1:     # 예외3. 길이가 1인 나무 밖에 없을 때
    print(1)
else:       # 예외4. 나무가 1개 밖에 없을 떄
    print(v[0] - m)

리스트를 정렬한 뒤 가장 긴 나무부터 작은 나무 순으로 내려오며, 총 길이를 계산한다. 만약 총 길이가 m보다 커지면, 커진 값을 지나온 나무의 숫자만큼 나누어서, 현재 나무 길이에 더해주면 끝이다.

문제의 분류가 이진 탐색인데, 이진 탐색으로 어떻게 구현할 수 있는 지 모르겠다.