[백준 2805] 나무자르기 (python)

2805번: 나무 자르기

---

이분탐색을 이용한다.

시간초과가 났었는데 가져갈 수 있는 나무 개수가 목표량보다 넘어갈 때 그만 세니 통과되었다. (16~17줄)

 

1. left=0, right= 제일 긴 나무
2. 이분 탐색
3. 자른 나무들의 합을 세다가 목표량이 된다면 stop
4. 목표량을 넘었다면 answer을 설정해준다.
5. 합과 목표량을 비교해 left, right를 설정

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = list(map(int, input().split()))

left = 0
right = max(arr)
answer = 0
while left <= right:
    mid = (left+right) // 2
    _sum = 0
    for i in arr:
        if mid < i:
            _sum += i-mid
            if _sum > M:
                break

    if _sum < M:
        right = mid - 1
    else:
        answer = mid
        left = mid + 1

print(answer)