글 읽기 - 파이썬 골드바흐 추측문제 자꾸 시간초과가 뜹니다.

flame623 3년 전 0

4부터 10000까지 모든 짝수케이스에 대해 테스트해봐도 바로 답이 나오는데 왜 시간초과가 나오는지 모르겠습니다.

P = [2]
def make(n):
    global P
    for i in range(3,n):
        count = 0
        for j in P:
            if j > i**0.5:
                break
            if i%j==0:
                count +=1
                break
        if count == 0:
            P.append(i)

n = int(input())
NL = [int(input()) for i in range(n)]
make(max(NL))

for num in NL:
    L = sorted([(prime, num- prime) for prime in P if num - prime in P and prime <= num//2], key = lambda x:x[0]-x[1])
    print(L[-1][0], L[-1][1])

shg9411 3년 전 1

20번 라인이 불필요하게 많은 연산을 합니다.

list에서 in연산은 O(N)이 소요되며, 모든 쌍을 구할 필요도 없습니다.

flame623 3년 전 0

범위를 조정해서 통과할수 있었습니다. 감사합니다.

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

문제

문제

출처

ICPC

파이썬 골드바흐 추측문제 자꾸 시간초과가 뜹니다.

flame623 3년 전 0

shg9411 3년 전 1

flame623 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말