[BOJ][python] 2805. 나무 자르기

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

2805번: 나무 자르기

---

💡IDEA

이분 탐색을 사용하는 문제이다.

이분 탐색이란 가장 작은 값과 가장 큰 값을 기준으로 가운데 값을 찾아 타겟값을 비교하여 좌우 변수를 조정하며 탐색하는 방법이다. 

이 문제에서는 가운데 값보다 큰 높이의 나무를 잘라낸 합으로 비교하며 좌우 변수를 좁힌다.

절단기에 설정할 수 있는 최대 높이를 구하기 위해 구한 합과 타겟값을 비교하며 가장 큰 높이를 찾는다.

 

📌CODE

import sys
input = sys.stdin.readline

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

l, r = 0, max(heights)
ans = 0

while l <= r:
    m = (l+r)//2
    res = sum(h-m if m<h else 0 for h in heights)
    if res >= M:
        ans = max(ans, m)
        l = m+1
    else:
        r = m-1

print(ans)