백준 2805 나무 자르기 (Python)

 

import sys

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

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


def cut(height):
    result = 0
    for i in tree:
        result += max(0, i - height)
    return result


left, right = 0, max(tree)

while left <= right:
    mid = (left + right) // 2
    cur_height = cut(mid)

    if cur_height >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)

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

2805번: 나무 자르기

백준 이분 탐색 중에 가장 많이 푼 문제 중 하나일 거 같다.

그냥 Left, Right를 잡고 범위를 좁혀나간 후 푸는 이분탐색 문제이다.

 

얻을 수 있는 나무의 길이를 구하기 위해 높이에 따라 얻는 나무를 구해주는 함수는 만들어서 사용했다.