백준 2805 | 이진탐색 | 나무 자르기 [파이썬 python]

2805번: 나무 자르기

 

코드

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

# 이진 탐색을 위한 시작점, 끝점
start = 0
end = max(tree)

result = 0 # 최종 절단기 높이
while(start <= end):
    total = 0 # 가져갈 나무의 길이
    mid = (start + end) // 2 # 절단기 높이
    for i in tree:
        if i > mid: # 절단기보다 주어진 나무가 길면 자른 나머지를 total에 추가
            total += i - mid
            
    # 이진 탐색        
    if total < m: # 가져가야 하는 길이 m보다 작은 길이이면
        end = mid - 1 # mid 기준 왼쪽 부분 탐색
    else: # 가져가야 하는 길이 m보다 크거나 같으면
        result = mid # 절단기 높이를 mid로 설정
        start = mid + 1 # mid 기준 오른쪽 부분 탐색

print(result)

 

최소 M을 가져갈 수 있는 최대 절단기의 높이 result를 구해야 한다.

여기서 이진 탐색은 가져갈 나무의 길이(total)가 M이 되는 경우를 찾아야 하기 때문에 total에 대해 실행한다.

 

total은 주어진 나무를 절단기(mid)로 잘랐을 때 남는 길이가 된다.

그러므로 tree의 모든 요소를 절단기(mid)로 잘랐을 때 남는 길이인 i-mid를 total에 누적시킨다. 

 

이렇게 구해진 total을 가지고 이진탐색을 수행한다.

가져가야 하는 길이인 M과 비교해, total < M이면 M 기준으로 왼쪽 부분을 탐색해야 하므로 end를 mid-1로 바꿔 이진탐색을 계속 진행한다.

반대로, total > M이면 M 기준으로 오른쪽 부분을 탐색해야 하므로 start를 mid+1로 바꿔 이진탐색을 계속 진행한다.