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

[백준] 나무 자르기 2805번

나의 풀이

N, M = map(int, input().split())
trees = list(map(int, input().split()))
start = 1
end = max(trees)
def binary_search(arr, start, end):
    while start <= end:
        m_tree = 0
        mid = (start + end) // 2
        for x in arr:
            if x >= mid:
                m_tree += x - mid
        if m_tree >= M:
            start = mid + 1
        else:
            end = mid - 1
    return end
print(binary_search(trees, start, end))

• 이전 랜선 자르기와 비슷한 유형이였다.
• 입력값을 모두 받아주고 start 는 1 end 는 가장 긴 나무의 값을 담아준다.
• binary_search 함수를 만들어준다.
• 함수는 start 가 end 보다 작거나 같은 동안 반복되며, trees 를 돌면서 만약 mid 값이 나무보다 작거나 같다면 trees 에서 mid 를 뺀 값을 m_tree 변수에 더해준다.
• 만약 m_tree 의 길이가 M 보다 크거나 같다면 start 를 mid + 1 해준다.
• 아니라면 end 를 mid - 1 해준다.
• 이 과정을 반복하다 start 가 end 보다 커진다면 반복을 종료하고 최대값을 구해야 하기 때문에 end 를 반환한다.