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

이진탐색 문제

• 입력 받아야 할 값과 데이터가 크기 때문에 이진탐색을 고려하였다.
• 입력 값을 빠르게 받기위해 sys.stdin.readline().rstrip() 함수를 사용한다.
• 시간 초과가 날 경우 pypy를 이용한다.
• 예 아니오로 나눌 수 있는 파라메틱 서치 문제는 재귀적으로 하는 것보다 반복문으로 푸는 것이 더 깔끔하다.

# 예 아니오로 나눌 수 있는 파라메틱 서치 문제는 재귀적으로 하는 것보다 반복문으로 푸는 것이 더 깔끔하다.
import sys

n , m = list(map(int,sys.stdin.readline().rstrip().split())) # 나무 개수 n, 필요한 나무 길이 m

array = list(map(int,sys.stdin.readline().rstrip().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행(반복적)
answer = 0
while start <= end:
    remain = 0
    mid = (start + end) // 2 # 10
    for x in array:
        # 잘랐을 때의 남은 나무길이 계산
        if x > mid:
            remain += x - mid
    if remain < m: # 목표값 보다 모자르니 더많이 자르기
        end = mid - 1
    else: # 충분할 경우 덜 짜르기
        answer = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에 result에 기록
        start = mid + 1
print(answer)

스케치