나무 자르기 ( 2805 번 )

2805번: 나무 자르기

 

---

🧠 알고리즘

• 이분 탐색 (Binary Search)

 

✔️ 동작 방식

[ 핵심 아이디어 ]

• 나무를 어떤 높이(now_h) 로 자를지를 기준으로
  → 잘린 나무의 총 길이가 M 이상인지 판단한다.
• 가능한 절단 높이 중 최댓값을 찾는 문제이므로
  → 조건을 만족하면 더 높게 자르기,
  → 불만족하면 절단 높이를 낮춘다.

 

 

[ 로직 요약 ]

• 가능한 절단 높이의 범위를 l = 0, r = max(n_tuple)로 설정
• now_h = (l + r) // 2 를 현재 절단 높이로 설정
• 모든 나무에 대해 i > now_h 인 경우만 (i - now_h) 만큼 잘린 나무 길이를 합산
• 잘린 나무 총 길이가 m 이상이면 → 현재 높이는 가능 → answer 갱신 → 더 높은 절단 높이 탐색 (l = now_h + 1)
• 부족하면 → 절단 높이를 낮춤 (r = now_h - 1)
• 탐색 종료 후 answer 출력

---

 

🧾 코드

import sys

def _main():
    l, r = 0, max(n_tuple)

    while l <= r:
        now_h = (l + r) // 2
        now_tree = sum(i - now_h for i in n_tuple if i > now_h)

        if now_tree >= m:
            answer = now_h
            l = now_h + 1
        else:
            r = now_h - 1

    return answer
            
    
n, m = map(int, sys.stdin.readline().rstrip().split())
n_tuple = tuple(map(int, sys.stdin.readline().rstrip().split()))

print(_main())

---

 

⏱️ 시간 복잡도

while l <= r : 이분 탐색을 통한 최대 절단 높이를 찾기 ( 로그 시간 복잡도 )
    now_tree = sum(i - now_h for i in n_tuple if i > now_h) : 각 단계 마다 모든 나무 순회 ( 선형 시간 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )