[ BOJ 2805 ] 나무 자르기(Python)

문제

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

나무가 m 미터 이상 필요할 때, 절단기의 최대 높이 h를 구하는 문제다. 🌍💦

문제 풀이

이진 탐색 은 정렬된 배열에서 타겟을 찾는 알고리즘으로, O(log n)의 시간복잡도를 가진다.

투 포인터로 배열의 범위를 절반씩 좁혀가며 탐색하면 편하다.

1. 배열의 범위 정하기

l = 0
r = max(trees)

2. 중간값 h을 이용해 값을 구하고, 범위를 좁혀줄 것이다.

h = (l + r ) // 2

3. h 보다 높아 절단 된 나무의 길이를 모두 더해준다.

total = sum( t-h if h < t else 0 for t in trees)

4. 절단된 나무들의 길이가 목표치와 같거나, 목표치보다 클 때
   4-1. h의 값을 check 변수에 할당한다.
   4-2. l을 h + 1 로 할당시켜 범위를 좁혀준다.
   ( l의 값이 커진다 = h의 값이 증가한다 = 절단된 나무의 길이가 작아진다.)

if total >= m:
   check = max(check, h)
   l = h + 1

5. 절단된 나무들의 길이가 목표치보다 작을 때
   5-1. r을 h - 1 로 할당시켜 범위를 좁혀준다.
   ( r의 값이 작아진다 = h의 값이 감소한다 = 절단된 나무의 길이가 길어진다.)

else:
   r = h - 1

코드

import sys
input = sys.stdin.readline

# 나무 m미터가 필요, 절단기 높이 h
# 높이가 h보다 큰 나무들이 잘림

# 나무의 수 n, 필요한 나무 m
n, m = map(int, input().rsplit())
trees = list(map(int, input().rsplit()))

l, r = 0, max(trees)
check = 0

while l <= r:
    h = (l + r) // 2
    total = sum(t-h if h < t else 0 for t in trees)
    if total >= m:
        check = max(check, h)
        l = h + 1
    else:
        r = h - 1

print(check)