접근법
start를 0으로 설정하고 trees에서 가장 높은 나무를 max()함수로 찾아 end로 설정한다.
for문으로 trees에 있는 나무들을 하나씩 꺼내며 mid값과 비교하며 자른다(cut_tree에 저장).
만약 나무가 M보다 많이 잘렸다면(if cut_tree >= M) mid 값을 키운다.
"""이분탐색"""
from sys import stdin
N, M = map(int, stdin.readline().split()) # N = 나무 수, M = 집으로 가져갈 나무 길이
trees = list(map(int, stdin.readline().split()))
start, end = 0, max(trees) # 이분탐색용 왼쪽 오른쪽 설정
while start <= end:
mid = (start+end)//2
cut_tree = 0 # 잘린 나무 합을 저장하기 위한 변수
for i in trees:
if i > mid: # mid보다 큰 높이의 나무는 잘림
cut_tree += i - mid
if cut_tree >= M: # 원하는 나무 높이보다 더 많이 잘렸다면 start에 mid+1 입력
start = mid + 1
else: # 원하는 나무 높이보다 덜 잘렸다면 end에 mid-1 입력
end = mid - 1
print(end)
과제
CPython의 경우 시간초과로 실패가 뜬다. 개선하는 방법을 공부해야겠다.
