#393 백준 파이썬 [2805] 나무 자르기 - 이분탐색

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

 

SOLUTION

이분탐색으로 풀 수 있는 문제다.

정답비율이 난리나 있는 이유는 (아마) 초보자들이 선뜻 덤볐다가 시간 초과 폭탄을 맞지 않았나 하는 생각이 든다ㅎㅎ(본인 포함)

이분탐색에 대한 정의를 알고 오길 추천한다. (https://claude-u.tistory.com/267)

 

알고리즘은 쉽다.

벌목 높이를 움직여 필요 나무 길이를 채우는지 보는 것이다.

 

1) 가장 짧은 길이 1을 start로, 나무 중 가장 긴 길이를 end로 둔다.

2) 이분탐색이 끝날 때까지 while 문을 돌린다.

 

3) mid를 start와 end의 중간으로 두고, 모든 값에서 mid를 빼 총 어느정도 길이의 벌목된 나무가 나오나 살펴본다.

4-1) 벌목나무가 목표치 이상이면 mid+1을 start로 두고 다시 while문 반복

4-2) 벌목나무가 목표치 이하면 mid-1을 end로 두고 다시 while문 반복

5) start와 end가 같아지면: 조건을 만족하는 최대의 나무 절단 높이를 찾으면 탈출한다.

6) 결과값인 end출력

PYTHON CODE(pypy3)

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
    
    #벌목 높이를 이분탐색
    if log >= M:
        start = mid + 1
    else:
        end = mid - 1
print(end)