백준 2805번 나무 자르기

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

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

start = 0
end = max(tree)

while True:
  middle = (start + end) // 2
  res = 0

  for t in tree:
    if t - middle >= 0:
      res += t - middle

  if res == M:
    break

  elif res > M:
    start = middle

  else:
    end = middle

print(middle)

이분 탐색을 이해한대로 코드를 작성하였지만 역시나 시간 초과!!
어느 순간부터 시간 초과도 신경 써줘야하는 단계로 온 것 같다..

하지만 시간을 어떻게 줄일 수 있는 몰라서 검색을 해봤다.

그래서 나온 개념이 파이썬의 리스트 내포 였다.

일단 리스트 내포는 간단하게 말하자면 리스트에 있는 요소들을 계산해서 더 할 때, 한줄에 작성 해주게 되는데 속도가 더 빠르다고 한다. 근데 이렇게 작성해도 시간 초과가 떳다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

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

start = 0
end = max(tree)
answer = 0

while start <= end:
  middle = (start + end) // 2
  res = 0

  res = sum([t-middle if middle < t else 0 for t in tree])

  if res >= M:
    answer = middle
    start = middle + 1

  else:
    end = middle - 1

print(answer)

최종 코드

최종적으로는 start <= end 조건을 설정하고 start와 end의 값을 middle에 각각 1씩 더하고 빼는 과정을 통해 정답을 구했다.

기존에는 if문을 통해서 원하는 조건이 나오면 종료하는 방식으로 했는데 차라리 while에 종료 조건을 걸어주는 방법으로 하니 시간 단축이 되는 것 같다.