[백준] 2805번 : 나무 자르기 (파이썬, pypy3)

문제

나의 최종 답안

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)

접근 방법

• 이분탐색 문제이므로 중간 값(mid)을 구해주면 된다.
• 자른 나무의 합이(t) 가져가야 할 길이(m)보다 큰지, 작은지에 따라 조건문을 설정해 줘야 한다.
• 만약 크다면 절단기의 시작 위치를(start)를 높여 필요한 만큼만 가져간다.
  작다면 절단기의 끝 위치(end)를 낮춰 가져가야 할 양을 늘려주어야 한다.

시간초과?

제출한 코드의 로직에는 큰 문제가 없다.
파이썬 코드로 이분 탐색 문제를 풀 때 pypy3로 풀면 더 빠르게 풀 수 있다고 한다.
따라서 pypy3로 제출하였다.
기존 코드에서 readline을 사용해 입출력 속도를 향상시켜 보았으나(두번째 제출) 동일하게 시간초과가 발생하였다.
파이썬을 사용할 때

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10000000)

를 사용해주는 방법도 있는 것 같다.