[Python] 백준 / silver / 2805 : 나무 자르기

문제 링크 : https://www.acmicpc.net/problem/2805

이진 탐색 문제. while 문 조건에서, left 와 right 가 같을 때 까지 탐색 해줘야한다. 왜냐하면 예를들어, left = 3 right = 4 이고 정답 인덱스가 4인경우 mid = 3 이기 때문에, left < right 로 조건을 건다면 답을 낼 수 없게 되기 때문이다.

이렇게 원소의 존재 여부를 판단하는 것이 아니라 범위를 좁혀가는 문제일 경우, while 문 안에 answer 라는 변수에 정답을 저장해가면서 푸는게 좋은 것 같다.

파이썬 코드

import sys
N, M = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))


def getTree(h):
    result = 0
    for t in tree:
        if h < t:
            result += (t - h)
    return result


left = 0
right = 10**9
answer = 0
while left <= right:
    mid = (left + right) // 2
    if M > getTree(mid):
        right = mid - 1
    elif M <= getTree(mid):
        answer = mid
        left = mid + 1


print(answer)