[백준] 나무 자르기 (2805번) - 이진 탐색

🔗 문제 링크

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


💻 코드

N, M = map(int, input().split())

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

def binary_search(target, start, end):
    result_max = 0  # 나무 높이의 합이 정확히 M으로 떨어지지 않을 때 최댓값
    while start <= end:
        result = 0
        mid = (start + end) // 2
        for i in tree:
            if i > mid:
                result += i - mid
        if result == target:
            return mid
        elif result > target :
            result_max = mid
            start = mid + 1
        else :
            end = mid - 1
    return result_max

print(binary_search(M, 0, max(tree)))

설계

나무의 높이의 합은 정확히 M이 되지 않을 수도 있다. 이때, 절단된 나무의 높이의 합이 M보다 크고 절단기에 설정할 수 있는 높이의 최댓값을 위의 코드에서 result > target일 때 구할 수 있으므로 result_max에 값을 저장해 놓고 반환한다.

좋은 웹페이지 즐겨찾기