백준 - 2805 나무 자르기 [이분탐색]

2805 나무 자르기

1. 문제유형

• Binary Search

2. 자료구조

• left (int): 가장 작은 트리의 높이
• right (int): 가장 높은 트리의 높이
• mid (int): 트리의 중간 높이

3. 해결과정

• ⭐ 실수한 점) 트리의 높이가 최대여야 나무를 가장 적게 가져간다.
• 따라서, 자른 나무 길이가 M보다 작을 경우 right의 크기를 감소시킨다.
• 반대로 자른 나무 길이가 M보다 클 경우, left 크기를 증가시켜 나무를 절약한다.
• ⭐ list(tree-mid for tree in trees if tree-mid>0)으로 계산한 뒤, sum 계산 시 시간 초과가 발생했다.
• 따라서 바로 sum(tree-mid for tree in trees if tree-mid>0)으로 계산해주니 바로 통과했다.

1. left, right로부터 mid를 계산 후 자른 나무 길이를 계산한다.
2. 자른 나무 길이가 m보다 작으면 right = mid-1로 높이를 낮춘다.
3. 자른 나무 길이가 m보다 크면 left = mid+1로 높이를 높이고 answer = mid를 저장한다.

n, m = map(int, input().split())
trees = list(map(int, input().split()))

left, right = 1, max(trees)
answer = 0

while left <= right:
    mid = (left+right)//2
    cuts = sum(tree-mid for tree in trees if tree-mid>0)

    if cuts < m:
        right = mid-1
    else:
        left = mid+1
        answer = mid

print(answer)