[알고리즘] 백준 파이썬 2805 나무 자르기

📍 문제 탐색하기

나무 자르기 문제는 상근이가 필요한 나무의 길이 MMM을 확보하기 위해 절단기의 높이 H를 조정하여, 나무를 절단한 후 가져갈 수 있는 최대 절단 높이를 찾는 문제이다.

각 나무의 높이보다 절단기 높이가 낮다면 해당 나무의 일부가 잘리며, 절단기 높이보다 낮은 나무는 잘리지 않는다.
M 이상의 나무를 가져갈 수 있는 절단기의 최댓값을 구하는 것이 목표이다.

---

문제 조건

• 나무 개수 N: 1≤N≤1,000,000
• 필요한 나무의 길이 M: 1≤M≤2,000,000,000
• 나무의 높이 hi​: 0≤hi≤1,000,000,0000
• 나무의 총 높이 합은 항상 M 이상이므로, 반드시 필요한 만큼 나무를 얻을 수 있음이 보장된다.

 

---

가능한 시간 복잡도

• 완전 탐색(브루트포스) 사용 시:
  • 최댓값을 1부터 나무의 최대 높이까지 반복하면, 최악의 경우 O(N×hmax)로 비효율적.
• 이분 탐색을 사용한 접근법:
  • 절단 높이를 이분 탐색으로 조정하면서 필요한 나무 길이를 확인 → O(Nlog⁡hmax)

이러한 접근법으로도 충분히 해결할 수 있다.

---

📍 코드 설계하기

1. 이분 탐색 적용
   • 절단기의 높이 범위를 설정: 0부터 max⁡(나무높이)까지.
   • 중간값(절단기 높이)을 설정하고, 해당 높이에서 확보할 수 있는 나무의 길이를 확인.
2. 나무 길이 확인 함수
   • 절단 높이 H를 기준으로, 잘린 나무의 길이를 계산.
   • 얻은 나무 길이가 M 이상이면 더 높은 절단 높이를 탐색.
3. 이분 탐색 진행
   • 원하는 길이를 충족하면 높이를 증가 (mid+1).
   • 충족하지 않으면 높이를 감소 (mid−1).

---

📍 시도 회차 및 수정 사항

import sys
input = sys.stdin.readline

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

start = 0
end = max(length)

result = 0

while start <= end:
    
    mid = (start + end) // 2
    
    cut = sum(namu - mid for namu in length if namu > mid)
        
    if cut >= M:
        result = mid
        start = mid + 1
    else:
        end = mid - 1
        
print(result)