[Python] 백준 알고리즘 문제풀이 :: 9020번

백준 알고리즘 9020번 골드바흐의 추측 문제풀이. 소수 분류에 있는 문제를 풀면서 시간초과가 엄청 많이 났다. 심지어 가장 시간 오래 걸릴 것 같은 경우를 파이참으로 돌렸을 땐 잘 나와도 백준에서 돌리면 시간초과가 나오는 경우가 많았다. 고생 좀 했다. 골드바흐의 추측은 2보다 큰 모든 짝수를 두 소수의 합으로 나타낼 수 있다는 것이다. 10000 이하의 수는 이미 증명이 됐다. 그에 해당하는 소수 조합을 출력하는 문제다.

문제

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

풀이

import sys
 
primes = []
for i in range(1, 10000):
    if i == 1:
        continue
    elif i == 2:
        primes.append(i)
    else:
        end = int(i ** 0.5) + 1
        flag = True
        for j in range(2, end):
            if i % j == 0:
                flag = False
                break
        if flag == True:
            primes.append(i)
lenPrimes = len(primes)
 
tc = int(sys.stdin.readline())
for t in range(0, tc):
    n = int(sys.stdin.readline())
    resultA, resultB = 0,0
 
    mid, idx = 0,0
    for i in range(0, lenPrimes):
        if primes[i] <= n/2 and primes[i] > mid:
            mid = primes[i]
            idx = i
        else:
            break
 
    while True:
        flag = 0
        for i in range(idx, lenPrimes):
            if mid + primes[i] == n:
                resultA = mid
                resultB = primes[i]
                flag = 1
                break
        if flag == 1:
            break
        else:
            idx -= 1
            mid = primes[idx]
 
    print("%d %d" % (resultA, resultB))

우선 실행 시간을 줄이기 위해 소수를 몽땅 구해놓는다. 어차피 10000 이하의 숫자를 두 소수의 합으로 표현하는 거니깐 각 소수는 10000보다 작을 것이다. 에라토스테네스의 체로 primes 리스트에 소수를 다 집어넣는다.

각 소수에 해당하는 resultA와 resultB 변수를 선언한다. resultA + resultB는 어떤 짝수가 되어야 한다. 그리고 각각 primes 리스트 안에 들어있다.

mid, idx를 선언한다. primes에 담긴 소수 중 n의 중간값에 가장 가까운 원소를 찾는 것이다. primes[i]가 n/2보다 같거나 작으면서, mid보다 큰 경우 prime[i]를 mid로, idx를 i로 교체한다. 아니면 break로 빠져나온다. primes[i]가 n/2보다 커지면 빠져나올 것이다. 그리고 그 때의 mid는 n/2보다 작은 소수 중 가장 큰 수일 것이다.

그리고 idx번 인덱스 이후의 소수 중 mid와 더해서 n이 되는 것이 있으면 flag를 1로 바꾸고 바로 for문에서 빠져나온다. 이 때 현재의 mid는 resultA로, primes[i]는 resultB로 선언한다.

만약 mid와 더해서 n이 되는 수가 없다면, idx를 하나 빼준다. 그리고 mid를 primes[idx]로 교체해준다. 즉 가운데에서부터 0으로 가까워지며 하나하나 구하는 것이다. 이러면 0부터 증가하는 것보다 더 빨리 찾을 수 있다.