글 읽기 - python 시간초과

wansang93 1년 전 0

아래와 코드와 같이 2진탐색으로 모든 부분문제를 찾는 선에서 pypy만 제출만이 통과되는데

python으로 시간초과가 납니다.ㅜㅜ 해당 알고리즘의 시간 복잡도의 저의 생각은 N 인데 왜 시간초과가 날까요?ㅜㅜ

n이 10^6인데 재귀함수를 써서 그런가요?

import sys
input = sys.stdin.readline
output = sys.stdout.write

n, m, a, c, x0 = map(int, input().split())
lst = [0] * n
MAX_V = 0
for i in range(n):
    lst[i] = (a * x0 + c) % m
    x0 = lst[i]
    MAX_V = max(MAX_V, x0)
ans = 0

def search(lo, hi, min_v, max_v):
    global ans
    if lo > hi:
        return
    
    mid = (lo + hi) // 2
    target = lst[mid]
    if min_v <= target <= max_v:
        # print(target)
        ans += 1

    search(lo, mid-1, min_v, min(max_v, target))
    search(mid+1, hi, max(min_v, target), max_v)

search(0, n-1, 0, MAX_V)
output(str(ans))

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

문제

문제

출처

ICPC

python 시간초과

wansang93 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말