n,m=map(int,input().split()) #나무의 수(n), 나무의 길이(m)
arr_h=list(map(int,input().split())) #나무의 높이(h)
start,end=1,max(arr_h)
while start<=end: #이분탐색
mid=(start+end)//2 #절단기의 중간값
t=0 #자른 나무의 합을 저장할 변수
for i in arr_h: #나무 높이 배열 접근
if i>=mid: #나무 높이가 절단기의 중간값보다 크거나 같으면
t=t+i-mid #나무를 자르고, 합을 저장
if t>=m: #자른 합이 필요한 것보다 크거나 같으면 절단기의 높이를 올림
start=mid+1
else:#아니라면 절단기의 높이를 낮춤
end=mid-1
print(end)
접근 방법
제출한 코드의 로직에는 큰 문제가 없다.
파이썬 코드로 이분 탐색 문제를 풀 때 pypy3로 풀면 더 빠르게 풀 수 있다고 한다.
따라서 pypy3로 제출하였다.
기존 코드에서 readline을 사용해 입출력 속도를 향상시켜 보았으나(두번째 제출) 동일하게 시간초과가 발생하였다.
파이썬을 사용할 때
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
를 사용해주는 방법도 있는 것 같다.