문제
나의 최종 답안
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)를 사용해주는 방법도 있는 것 같다.
