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

상근이가 M만큼의 나무를 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제.

 

이분 탐색(Binary Search)을 활용하는 문제이다.

최근에 문제들을 풀면서 시간 초과 때문에 막힌적이 많은데,

이 문제도 마찬가지이다.

 

시간 복잡도(Time Complexity)를 고려하며 코드를 짜는 연습을 해야겠다는 생각이 들었다.

 

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

def fn(target):
    start = 0
    end = max(trees)
    result = 0
    
    while start <= end:
        mid = (start + end) // 2
        s = sum(tree - mid for tree in trees if tree > mid)

        if s >= target:
            result = mid
            start = mid + 1
        else:
            end = mid - 1
    return result

print(fn(M))