[BOJ] 6588 - 골드바흐의 추측 (Python)

 

 

아이디어

 

에라토스테네스의 체로 소수를 판정하고, 메모이제이션을 사용하여 시간을 단축한다.

 

 

풀이

 

예전에 작성한 코드가 재채점 후 시간 초과가 되어 다시 풀어본 문제로,

메모이제이션이나 불필요한 과정을 생략하여 실행 시간을 줄여야 했다.

 

에라토스테네스의 체로 소수인 수의 인덱스는 True, 소수가 아닌 수의 인덱스는 False로 하는 리스트 p를 만든다.

이때 입력으로 주어지는 짝수 정수를 두 홀수 소수의 합으로 나타내면 되므로 홀수이면서 소수가 아닌 수만 확인한다.

따라서 i는 3부터 시작하여 2만큼 건너뛰고, j는 i*3에서 짝수 크기만큼 건너뛰어 홀수 인덱스만 확인하도록 한다.

 

메모이제이션을 위해 딕셔너리 memo를 만들고, n이 0이 아닐 때까지 while문을 반복한다.

n이 memo에 존재하면 그대로 출력하고, 그렇지 않으면 i를 작은 값부터 차례로 증가시키면서 두 홀수 소수를 찾는다.

두 홀수 소수를 찾으면 memo에 저장하고 출력한 후 break문으로 for문을 빠져 나온다.

 

import sys

input = sys.stdin.readline

def solution():
    p = [True]*1000001
    p[1] = False
    for i in range(3, 1001, 2):
        if p[i]:
            for j in range(i*3, 1000001, i*2):
                p[j] = False
    memo = dict()
    while 1:
        n = int(input())
        if n == 0:
            return
        res = memo.get(n, False)
        if res:
            print(res)
        else:
            for i in range(3, n, 2):
                if p[i] and p[n-i]:
                    memo[n] = f'{n} = {i} + {n-i}'
                    print(f'{n} = {i} + {n-i}')
                    break
            else:
                print('Goldbach\'s conjecture is wrong.')

solution()

 

 

메모이제이션을 사용하지 않으면 메모리는 더 적게 사용되지만 사용한 코드보다 약 3배 정도 느렸다.

# 메모리가 더 적게 사용되나 더 느린 코드
while 1:
    n = int(input())
    if n == 0:
        return
    for i in range(3, n, 2):
        if p[i] and p[n-i]:
            print(f'{n} = {i} + {n-i}')
            break
    else:
        print('Goldbach\'s conjecture is wrong.')

 

에라토스테네스의 체의 for문에서 스텝 값을 주어 건너뛰도록 한 코드가 메모리를 더 많이 사용하지만 더 빨랐다.

# 1.
for i in range(2, 1001):
    if p[i]:
        for j in range(i*2, 1000001, i):
            p[j] = False

# 2. 1번 코드보다 메모리를 더 많이 사용하지만 더 빠른 코드
for i in range(3, 1001, 2):
    if p[i]:
        for j in range(i*3, 1000001, i*2):
            p[j] = False