글 읽기 - python 시간초과 질문입니다!

happiness_1997 3년 전 0

안녕하세요!

제가 입력받은 값중 가장 큰 값에 대해서만 에라토스테네스의 체를 이용하여 한번 리스트화 한 후 골드바흐 파티션을 수행하였는데 계속 시간초과가 떠서 이렇게 질문드리게 되었습니다. 혹시 어떤 부분이 잘못된 부분인지 알려주시면 감사드리겠습니다! (제 생각에는 gold함수에 count가 문제인것 같은데 다른방법이 있을까요?)

t=int(input())

def decimal(n): #입력받은 값중 최대 값n에 대한 소수 리스트 반환
    arr=[True]*n
    k=int(n**(0.5))
    for i in range (2,k+1):
        if arr[i]==True:
            for j in range (i*2,n,i):
                arr[j]=False
    return [i for i in range (2,n) if arr[i]==True]

def gold(nn,result,t): #골드바흐 파티션수행
    a=[1,1]
    for i in range(t):
        min=nn[i]
        for j in result:
            if j>nn[i]//2: break
            k=nn[i]-j
            num=result.count(k)
            if num==1:
                if k-j<min: #합을 이루는 두 소수의 차가 가장 작은 값 대입
                    min=k-j
                    a.pop()
                    a.pop()
                    a.append(j)
                    a.append(k)
        print(a[0],a[1])           
nn=[]
for i in range (t):
    n=int(input())
    nn.append(n)
result=decimal(max(nn)) 
gold(nn,result,t)

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

문제

문제

출처

ICPC

python 시간초과 질문입니다!

happiness_1997 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말