[백준 2805번] 나무 자르기 - python

문제 링크

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

풀이 

- 이분 탐색 문제 

- 최대 범위가 매우 크므로 이분 탐색을 의심하도록 하자. 

- start = 1, end = 최대 나무 길이 

import sys 
input = sys.stdin.readline

n, m = map(int,input().split())

data = list(map(int,input().split()))

start =1 
end = max(data)

answer = 0 

while start <= end :
  mid = (start + end) // 2 
  tree = 0
  # 트리의 길이가 자를 길이보다 길면 남은 나무 길이 더하기 
  for i in data:
    if i > mid :
      tree += i - mid 
  
  # 가져갈 나무 길이가 m 보다 작으면 줄이기
  if tree < m :
    end = mid -1 
  else :
    answer = mid
    start = mid + 1 

print(answer)