[Baekjoon] 2805. 나무 자르기 (이진탐색)

나무 자르기

🔍 코드

# 나무 자르기

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

start = 1
end = max(trees)
result = 0

while start <= end:
    mid = (start + end) // 2

    #잘랐을 때 가져갈 수 있는 나무의 길이 계산
    length = 0
    for i in trees:
        if i > mid:
            length += i - mid
        
    if length >= m : #필요 이상의 나무길이
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

🔍 다른 코드

결과값으로 이진탐색의 끝점 end를 출력한다.

이 문제는 절단기에 설정할 수 있는 최대 높이를 구하는 것이 목표다.

이유 및 참고

# 나무 자르기

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

start = 1
end = max(trees)

while start <= end:
    mid = (start + end) // 2

    #잘랐을 때 가져갈 수 있는 나무의 길이 계산
    length = 0
    for i in trees:
        if i > mid:
            length += i - mid
        
    if length >= m : #필요 이상의 나무길이
        start = mid + 1
    else:
        end = mid - 1

print(end)

💫 Comment

'적어도 M미터의 나무'를 가져가야 한다고 했으므로 딱 M만큼 필요한 것이 아니라 M보다 크거나 같으면 된다.