Algorithm/Problems
99클럽 코테 스터디 6일차 TIL + 이분탐색
공부좀하시졍
2024. 11. 3. 01:00
https://www.acmicpc.net/problem/2805
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
trees = list(map(int, input().split()))
start = 0
end = max(trees)
answer = 0 # 절단기 높이
while start <= end:
mid = (start + end) // 2
total = 0
for t in trees:
if t > mid:
total += t - mid
if total >= m:
start = mid + 1
answer = mid
else:
end = mid - 1
print(answer)
- m과 n의 범위를 보고 이분탐색을 생각할 수 있다.
- 절단기 높이의 최댓값을 구하는 것이기 때문에 굳이 mid값을 초기화 해줄 필요 없이 end값이 답이 될 수 있다.