글 읽기 - python 시간초과

peterjw201 2년 전 0

60%까지 올라가다가 시간초과가 발생하는 코드입니다.

이 코드와 같은 코드로 몇 달 전 정답을 받았었는데 지금은 시간초과가 뜨는 이유가 뭘까요

n,m = map(int, input().split())
tree = list(map(int, input().split()))
start = 1
end = max(tree)
while start <= end:
    mid = (start + end) //2
    temp = 0
    for i in tree:
        if i > mid:
            temp += (i-mid)
    if temp >= m:
        start = mid+1
    else:
        end = mid-1
print(end)

wider93 2년 전 0

단순히 오래 걸려서 그렇습니다. while문 한 번에 end - start 가 대략 반으로 줄어드니까, 31번 정도 돌 수 있습니다. tree 개수가 최대 백만이니 3천만 번 정도 루프를 돕니다. 파이썬 덧셈은 2**30까지는 그럭저럭 빠른데 그 이상은 많이 느립니다.

참고로 8~10번 줄도 이분탐색을 할 수 있습니다. 시도해 보시면 좋을 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python 시간초과

peterjw201 2년 전 0

wider93 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말