백준 2805 나무 자르기

 

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

2805번: 나무 자르기

이분 탐색을 사용해야하는 알고리즘이며 관건은 입력받은 필요한 나무의 길이 M을 이분탐색의 조건에 사용해야 한다는 것이다. 만약 필요한 나무의 길이가 부족하다면 나무를 자르는 위치를 낮추어야 하고 나무의 길이가 너무 많다면 나무를 자르는 위치를 높이면 된다. 하지만 최대길이는 어떻게 구하는 걸까? 개인적으로 이부분이 가장 애를 먹었던 구간인데 잘 생각을 해보면 이분탐색의 start와 end에서 반복문이 끝나는 조건문은 while start <= end:가 되기에 end가 자르는 범위중에서 가장 큰 값이 될 것이다. 따라서 코드는 다음과 같이 작성된다.

import sys

N, M = map(int, sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))
start = 1
end = max(trees)

while start <= end:
  mid = (start + end) // 2
  tot = 0 #벌목한 나무의 총 길이
  #벌목한 나무의 총 길이 구하기
  for log in trees:
    if log >= mid:
      tot += log - mid
  #이분탐색 알고리즘
  if tot >= M:#만약 나무 총 길이가 너무 크다면
    start = mid + 1 #자르는 길이를 늘린다
  else:#만약 나무 총 길이가 작다면
    end = mid -1 #자르는 길이를 줄인다
print(end)#가장 마지막으로 자른길이가 최대길이가 된다

end의 경우 나무를 자르는 길이가 이미 배치된 나무들 중 최대길이보다 클 필요가 없다는 걸 생각해서 max(trees)로 설정한 것을 기억하자