백준 2805 - 나무 자르기 (Python3)

코드

n, m =  map(int, input().split())

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

start = 0
end = max(tree)

target = 0

while (start <= end):
    mid = (start + end) // 2
    
    tot_height = 0
    
#     for t in tree:
#         if t - mid > 0:
#             tot_height += (t - mid)

    tot_height = sum(t - mid if t > mid else 0 for i in tree)
    
    if tot_height == m:
        target = mid
        break
    
    if tot_height > m:
        start = mid + 1
        target = mid
    else:
        end = mid - 1

print(target) 

문제 해설

전형적인 이진탐색 문제이다.

이진 탐색

이 문제의 경우 시간 복잡도가 중요한 문제로 Pypy3으로 사용하는 경우 정답으로 인정이 된다. Python3으로 인정받기 위해서 기존의 for문을 List Comprehension 형식으로 사용하니까 시간 복잡도에서 더 성능적으로 우수하여 정답으로 인정받을 수 있었다.