[Python]수학2 백준 9020

문제

https://www.acmicpc.net/problem/9020

가장 먼저 드는 생각은 범위의 소수를 구해 모든 경우에 수에서 확인해보는것이다.

오늘은 시간초과로 많은 코드를 올려야 하는 관계로 실패한 부분은 파일로 올려놓아야겠다.

9020_fail_1.py

과정은 10000까지의 소수리스트를 만든후 소수인 수만 뽑은 후 둘개의 소수를 뽑아 더해

보는 방식으로 구현했다.O(N^2)의 시간이 걸릴것이다.

아래는 더 빠르게 찾기위해 중간부터 시작한 코드이다. 역시 O(N^2)이 걸린다. 속도는 반으

로 줄었겟지만 이런방법으로는 해결할수 없었다.

9020_fail_2.py

그래서 사용한 방법은 중간부터 시작하는데 n은 짝수이므로 무조건 n/2 는 자연수가 나온

다 그리고 두수의 합이 n이되기위해선n-x + n+x가 되어야 n이 될수있다. 중앙부터 x만큼 

줄이고 x만큼 늘린값이 소수 리스트에 둘다 있으면 출력하면 된다.

import sys
 
 
prime_number=[2 for _ in range(10001)]
 
for i in range(1,10001):        #소수리스트 만들기
 
    if i==1:
        prime_number[i]=0
    elif prime_number[i]!=0:
 
        prime_number[i]=1
        mul = 2
        j = i
        while(j*mul<=10000):
            prime_number[j*mul]=0
            mul+=1
 
T=int(sys.stdin.readline())
while(T>0):
    T-=1
    n=int(sys.stdin.readline())
    mid=n//2
    x=0
    for i in range(0,mid):    #중간값에서 1씩 줄여가며 소수리스트에 둘다 있으면 출력
        if prime_number[mid+x]+prime_number[mid-x]==2:
            print(str(mid-x)+" "+str(mid+x))
            break
        x+=1
 

이렇게 해주면 O(N)이고 시간초과가 더이상 뜨지않고 성공하는모습을 볼수있다.

여기서 조금만 더 조정해보자면

while(T>0):
    T-=1
    n=int(sys.stdin.readline())
    mid=n//2
    x=0
 
    if mid%2==0:
        x=1
    if mid==2:
        x=0
    for i in range(0,mid):
 
        if prime_number[mid+x]+prime_number[mid-x]==2:
            print(str(mid-x)+" "+str(mid+x))
            break
        x+=2
 

소수의 특성상 2를제외한 모든 소수는 홀수이다 1씩 더하지 않고 2씩더해가며 반복해도 

상관이없다.더 빠르게 할려면 모든경우의 수를 미리구해 메모리에 담아주면 가능할거 

같다. 5000*4*2byte정도의 메모리가 사용될것이기 때문에 충분히 가능하지 않을까 생각되

지만 굳이 시도해 보지는 않겠다.