[백준] 2805번 나무 자르기

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

이 문제는 이코테 이진 탐색 챕터의 떡볶이 떡 만들기 예제와 거의 똑같아서 금방 풀었다.

최종 나무의 길이와 필요한 나무의 높이를 비교하며 start, end 위치를 조정해나가면 풀 수 있다.

# 2805 : 나무 자르기

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

start, end = 0, max(height)

result = 0
while start <= end:
    total = 0
    mid = (start + end) // 2
    
    for x in height:
        if x > mid:
            total += x - mid
    if total < m:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

Uploaded by Notion2Tistory v1.1.0