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

백준 - 2805 나무 자르기

풀이

1. 이중 반복문을 돌려야하고 모든 수를 비교해야 하기 때문에 이진 탐색으로 해결해야 함

2. 정답 H의 범위는 1 ~ 트리의 최대 높이
   -> left: 1, right: max(trees) 로 범위를 지정해서 이진탐색

3. 높이 h = (left + right) / 2 로 지정(중간값) 후, h 높이로 잘랐을때 가져가는 나무의 총 길이(total)를 구해줌

4. total < M 이면 right 범위를, 그렇지 않으면 left 범위를 조절

5. left가 right 보다 커지면 중단

삽질

1. 맨 처음 접근법
   -> 1. 배열에서 인덱스로 left, right를 지정한 후
   -> 2. left = trees[left], right = trees[right] 로 다시 지정해서 같은 코드를 두 번 씀
   뭔가 이상하다고 느꼈다... 굳이 처음에 인덱스로 안해도 된 다는 걸 알고 바꿈!

2. left, right 숫자 조정시 주의
   처음에는 left = h, right = h를 넣어줬었다... 그런데 당연히 무한루프에 빠진다!
   left = 15, right = 15인 경우 h = 15이기 때문에 무한루프에 빠진다....................... (몰랐음)

코드

from sys import stdin

N, M = map(int, stdin.readline().split())
trees = list(map(int, stdin.readline().split()))

left = 1
right = max(trees)
while left <= right:
    h = (left + right) // 2
    total = sum([i-h for i in trees if i > h])
    if total < M:
        right = h - 1
    else:
        left = h + 1
print(right)