[백준][파이썬]2805번: 나무 자르기

문제 출처 : https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

내 풀이

import sys
input = sys.stdin.readline

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

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

start = 0
end = max(high)

while start <= end:
    mid = (start + end) // 2
    cnt = 0
    cnt = sum(i - mid if i - mid > 0 else 0 for i in high)
    
    if cnt < m:
        end = mid - 1
    else:
        start = mid + 1

print(end)

설명

단순히 이분 탐색으로 풀면 통과될 줄 알았는데 pypy3로는 통과되지만 python3에서는 계속 시간초과가 나서 해맸다.

중간에 cnt를 계산해주는 반복문에서 시간초과가 나던 것이었는데 이를 sum으로 해서 약간 변형을 주었더니 해결되었다. 왜 이게 더 빠른지 아직은 정확히 몰라서 좀 더 공부하고 고민해봐야할 것 같다.