[백준] 2805: 나무 자르기 (파이썬, 이분 탐색)

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

▶ 구해야하는 것

• 입력: 나무의 수: N, 자를 나무의 총 길이: M (나무의 길이는 최대 2억...)
           N개의 나무의 높이 (1억 보다 작거나 0이상이다)
• 출력: 적어도 M만큼 가져가기 위해 설정한 높이의 최댓값(H)을 찾는다.!!

▶ 풀이 탐색

O(log H): 나무의 높이(H)를 이분 탐색한다.

O(N): 각 나무마다 잘릴 수 있는지 확인한다.

총 O(NlogH)의 시간 복잡도가 소요된다. 약 천만 이므로 시간 제한에 어긋나지 않음

---

아이디어:

 목재절단기 H가 클수록 가져갈 수 있는 나무 길이는 작아지고,  H가 작을수록 커진다.

1. 적절한 높이(H)를 찾을 때까지 이진탐색을 수행하며 반복해서 H를 조정한다.
2. 현재 이 높이로 자르면 조건을 만족할 수 있는가를 확인한 후에 조건의 만족 여부에 따라 탐색 범위를 좁힌다.
3. 중간값을 최적화한다.

▶ 코드 설계

import sys
from bisect import bisect_left, bisect_right

N, M = map(int, sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))

start = 0
end = max(trees)

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

print(result)

 

▶ 추가 풀이