백준 2805번 나무자르기

이 문제도 이분 탐색 문제로 최대값과 최소값을 잘 설정한뒤에 이분 탐색을 하면된다 python으로 제출할시에 시간초과가 나와서 pypy3로 제출했다

 

 

문제 해결

먼저 최대값은 최대나무의 길이를 넣고 max함수를 사용한다

최소값은 1로 설정한뒤에 이뷴 탐색을 하고 결과를 구하면 된다 이분 탐색이지만 python으로 돌리면 시간 초과가 나오닌 pypy3로 돌리자

pypy3인 경우 파이썬과다르게 변수를 선언하지 않고 사용하면 런타임 에러 (name error)가 출력되니까 주의

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

tree = list(map(int,sys.stdin.readline().split()))

start = 1
end = max(tree)
result = 0

while start <= end:
    mid = (start + end ) // 2
    c = 0 #잘린 나무의 길이

    for i in tree:
        if i > mid:
            c += i - mid
    
    if c >= M:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)