[Python]백준 2805번 - 나무 자르기

1. 문제정보

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

2805번: 나무 자르기

 

 

2. 해결전략

가장 쉽게 가장 큰 나무의 길이부터 1씩 감소시키면서 비교하는 방법이 있지만 나무 높이의 최대값이 20억이기 때문에 이 방법은 시간 초과가 발생할 것이라고 생각했습니다. 때문에 최적의 높이를 찾은 후 비교 연산을 수행하는 방법이 있고 최적의 높이를 찾아내기 위해 이분 탐색 알고리즘을 사용했습니다.

 

 

3. 코드

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

start = 0
end = max(trees)
def binary_search(trees, target, start, end):
    result = 0
    while start <= end:
        mid = (start + end) // 2
        total = 0
        for tree in trees:
            if tree > mid:
                total += (tree-mid)
        
        if total  < target:
            end = mid-1
        else:
            if result < mid:
                result = mid
            start = mid + 1
    return result
    

result = binary_search(trees, M, start, end)
print(result)