백준 2805: 나무 자르기 (Python)

 

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

이진탐색 알고리즘 공부하면서 풀었던 문제랑 똑같네! 하고

후다닥 풀었지만 50%에서 시간 초과..

시간을 줄이고자 이리저리 고쳐봤지만 더이상 고칠게 없는 거 같은데도 시간 초과..

결국 구글링.. 이진 탐색으로 풀면 pypy3로 제출해야 시간초과가 뜨지 않는다고 한다ㅠ

Counter 라이브러리 쓰면 python3도 통과된다고 하긴 함..

 

import sys

n, m = map(int, sys.stdin.readline().split())
h = list(map(int, sys.stdin.readline().split()))

start = 0
end = max(h)

while start <= end:
    cut = 0
    mid = (start + end) // 2

    for i in h:
        if mid < i:
            cut += i - mid

    if cut >= m:
        start = mid + 1
    else:
        end = mid - 1

print(end)

 

차암나