[백준] 2805. 나무 자르기 (Python)

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

2805번: 나무 자르기

 

✏️ 이분탐색 문제!

✏️ 이분탐색을 통해 가장 적절한 절단기 높이를 구하는 문제였다.

✏️ 나무의 높이가 0부터 1000000000 사이이므로, s를 0, e를 가장 높은 나무의 높이로 두었다.
✏️ 이분탐색의 기본 개념을 복습하기에 좋은 문제였다.

 

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

# 나무의 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0 => s는 0, e는 가장 높은 나무의 높이
s = 0
e = max(trees)

# 이분 탐색
while s <= e:
    mid = (s+e)//2
    # 잘라낼 수 있는 나무의 길이 합 구하기
    temp = sum(tree-mid for tree in trees if tree-mid>0)
    # 나무를 더 많이 잘라버렸다면 절단기 높이를 높여야 하므로 s를 mid+1로 옮겨줌
    if temp >= M:
        s = mid+1
    # 나무를 덜 잘랐다면 절단기 높이를 낮춰야 하므로 e를 mid-1로 옮겨줌
    else:
        e = mid-1

print(e)