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

• 유형 : 이분 탐색

설명

• 나무를 아래 그림과 같이 자르는 상황이다.

 

• 절단할 높이 H를 기준으로 이분 탐색을 한다.
• H만큼 나무를 자르고, 위에 남은 윗부분을 다 합친다(tree_sum). 상근이는 이걸 집에 가져가는 거다.
• tree_sum과 필요한 나무(m)를 비교한다. 
  • tree_sum이 m 이상이면 : 상근이가 원하는 조건을 만족한다. 현재까지의 정답 중 최댓값으로 업데이트한다. 하지만 우린 '최적의 값', 여기서는 '최댓값'을 찾아야 하기 때문에 h를 늘려서 다시 이분 탐색을 한다.
  • tree_sum이 m보다 작으면 : 나무가 부족하다. 상근이가 원하는 조건을 만족하지 못한다. 나무를 더 베어야 하므로, h를 줄여서 이분 탐색한다.

코드 (Python)

# 입력받기
n, m = map(int, input().split(' ') )
trees = list( map(int, input().split(' ')) )

# h를 기준으로 이분탐색 시작
ans = 0
left = 0
right = max(trees) # right 초기값은 나무 높이들 중 max

while left<=right :
    mid = (left + right) // 2
    
    # 1. 나무 자르기
    tree_sum = 0
    for tree in trees:
        if tree > mid:
            tree_sum += tree-mid

    # 2. m과 비교
    if tree_sum >= m:
        ans = max(mid, ans)

        # h를 늘려서 탐색한다. (최적해 찾아가기)
        left = mid+1
    else:
        # h를 줄여서 탐색한다. (나무가 모자라니까)
        right = mid-1

# 정답 출력
print(ans)

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

2805번: 나무 자르기