[백준] 2805. 나무 자르기 (파이썬)

🗂️   문제 

2805. 나무 자르기

---

---

📌   Point

Binary Search

절단기 높이 H를 이진 탐색으로 조정하며, 잘린 나무의 합이 M 이상인지 확인한다.

 

• 조건을 만족하면 더 높은 높이도 가능하므로 높이를 올린다. (left = mid + 1)
• 조건을 만족하지 못하면 더 낮은 높이로 내려야 한다. (right = mid - 1)

 

---

📄   코드

def solution():
    N, M = map(int, input().split())
    trees = list(map(int, input().split()))

    def is_enough(height):
        return sum((tree - height) for tree in trees if tree > height) >= M

    left, right = 0, max(trees)
    result = 0

    while left <= right:
        mid = (left + right) // 2
        if is_enough(mid):
            result = mid
            left = mid + 1
        else:
            right = mid - 1

    print(result)

solution()

---

✍🏻   풀이

시간 복잡도 : O(N × log(max trees))

 

1. function : is_enough(height)
   • 현재 높이 height로 절단기를 설정했을 때, 잘려 나오는 나무 길이 총합을 계산
   • 합이 M 이상이면 True 반환
2. binary search
   • 이진 탐색 범위 : 0 ~ 가장 높은 나무 높이
   • 조건을 만족하는 가장 큰 높이를 찾는다.
     
     • 매번 is_enough를 호출해 조건을 확인하고 범위를 조절한다.
     • 조건을 만족하면 더 높은 높이도 가능하므로 left = mid + 1
     • 조건을 만족하지 않으면 더 낮은 높이로 right = mid - 1