[이분탐색] 백준 2805번 나무 자르기 with Python3 ★★

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

2805번: 나무 자르기

 

문제

 

정답 풀이

N, M = map(int, input().split())
tree = list(map(int, input().split()))
start, end = 1, max(tree) #이분탐색 검색 범위 설정

while start <= end: #적절한 벌목 높이를 찾는 알고리즘
    mid = (start+end) // 2
    
    log = 0 #벌목된 나무 총합
    for i in tree:
        if i >= mid:
            log += i - mid #i높이 이상의 나무들을 모두 잘라서 log값에 더해주는 과정
    
    #벌목 높이를 이분탐색
    if log >= M:
        start = mid + 1
    else:
        end = mid - 1
print(end)

출처: https://claude-u.tistory.com/446

해설

적절한 조건을 만들 자신이 없어서 답부터 봤다.

 

 

 

두번째 예제 시각화

 

print순서는 mid, log, start/end 순

5 20
4 42 40 26 46 #입력

mid:23
log:62
start:24, end:46

mid:35
log:23
start:36, end:46

mid:41
log:6
start:36, end:40

mid:38
log:14
start:36, end:37

mid:36
log:20
start:37, end:37

mid:37
log:17
start:37, end:36

36 #답

보면 알겠지만, log값이 M이랑 일치할 때 멈추지 않는다 while문은.

반드시 start가 end보다 더 커질때까지 돌게되어있고,

 

그 경우 end값을 출력한다는 것은 

 

무조건, M만큼은 가져갈수있는 최대 높이임을 보증하는 로직.

 

검색과 다르게 탐색이기에 이런식으로 활용한다는게 놀랍다.