[백준 2805번] 나무 자르기 (파이썬/python)

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

2805번: 나무 자르기

 

솔직히 이분탐색을 구현해본적이 많지 않아서... 상당히 고전한 문제

이분탐색으로 반씩 줄여가며 풀어야 제한시간 내에 풀 수 있다.

 

내가 쓴 코드는 pypy3으로 제출해야 시간초과 안남

python3으로 내면 시간초과남

 

 

import sys
 
input = sys.stdin.readline
 
n, m = map(int, input().split())
woods = list(map(int, input().split()))
 
left = 0
right = max(woods)
result = []
while left <= right:
    sum_length = 0
 
    mid = (left + right) // 2
    for i in woods:
        if i > mid:
            sum_length += i - mid
 
    if sum_length == m:
        result.append(mid)
        break
    elif sum_length > m:
        result.append(mid)
        left = mid + 1
    else:
        right = mid - 1
 
print(max(result))