글 읽기 - 파이썬 시간초과,,

ie1914 4년 전 1

질문 목록 보면서 시간 낭비하는 요소들을 다 제외했는데도,

아직 시간초과가 4%때 나네요,,,

받은 수 중 제일 큰 수를 기준으로 소수 목록 만들었고,

각 수마다 필요한 만큼 잘라서 비교하고,

목표 짝수를 구성하는 두 수의 후보들중 차가 제일 작은 것을 찾았습니다.

원래 in 있었는데, 시간 많이 걸린다고 하셔서 없앴고,

할 수 있는 시도는 다 해봤는데, 안되네요.

4,10000 잘되고

N=3 4 10000 5000 모두 잘됩니다.

어디가 문제인 걸까요?

import sys

N=int(sys.stdin.readline())
li=[None]*N
for i in range(N):
    li[i]=int(sys.stdin.readline())

max_val = max(li)

sieve =[True]*(max_val+1) 
m = int((max_val)**0.5)+1 
sieve[1]=False 
for i in range(2,m+1):
    if sieve[i] == True :
        for j in range(i+i,max_val+1,i):
            sieve[j] = False
lis = [i for i in range(1,max_val+1) if sieve[i] == True]
#소수목록을 제일큰기준으로 딱 한번만듬

# print(lis)
for k in li:
    z=0
    while lis[z]<=k and z<len(lis)-1:
        z+=1
    lili=lis[:z+1]
    # 필요한 만큼 소수목록을 자름
    ans=[]
    a=0
    for i in range(len(lili)) :
        j=len(lili)-1
        while lili[i]+lili[j]>=k and j>=0:
            if lili[i]+lili[j] == k:
                # print("test",lis[i],lis[j])
                ans.append([lili[i], lili[j]])
                break
            else :
                j-=1
    # print(ans)
    min_val=float('inf')#초기화
    min_li=[]
    for i in ans :
        if abs(i[1]-i[0])<min_val:
            min_val = abs(i[1]-i[0])
            min_li =[i[0],i[1]]
    # 후보군 중에서 차가 제일 적은 것을 찾음
    # min_li.sort()
    # print(min_li)
    print("%d %d"%(min_li[0],min_li[1]))

hello70825 4년 전 0

29줄~37줄에서 굳이 하나하나 lili[j]로 확인해서 k와 일치하는지 확인해야할까요?

잘생각해보시면 이미 만들어진 것을 활용하여 j없이 i 하나로 만드실 수 있습니다.

그래도 잘모르시겠다면 이것을 보시면 됩니다.

ie1914 4년 전 1

와,, 후배의 성장을 위한 조그마한 배려에

초보는 울고 갑니다.

정말 감사합니다!!

ie1914 4년 전 0

맞혔어요!!! 정말루 감사드립니다 ㅠㅠ 5시간동안 헤멨는데,,

그보다 문제의 완성도도 정말 ㅎㄷㄷ 하네요,,

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

문제

문제

출처

ICPC

파이썬 시간초과,,

ie1914 4년 전 1

hello70825 4년 전 0

ie1914 4년 전 1

ie1914 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말