백준_python 2805번 나무 자르기 (이분 탐색, 시간초과)

<문제 링크>

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

 

 

<정답 코드>

n, m = map(int, input().split())
trees = list(map(int, input().split()))
 
start, end = 1, max(trees)
 
while start <= end:
    mid = (start + end) // 2
 
    log_sum = 0     # 현재 높이에서 벌목 나무 합
    for i in trees:
        if i >= mid:
            log_sum += i - mid
    
    if log_sum >= m:
        start = mid + 1
    else:
        end = mid -1
 
print(end)

 

단순하게 for문으로 높이를 1씩 줄이면서 정답 찾으면 시간초과 발생

 

전체의 중간 값을 비교하며 검색 범위를 반씩 줄여나가는 이분탐색으로 해결