백준 문제 풀이 - 골드바흐의 추측 9020번

📜 문제 이해하기

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.
골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.
2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

💡 문제 재정의

2보다 큰 짝수가 주어졌을 때 두 소수의 합으로 출력해라.
여러 경우의 수가 존재할 때 두 수의 거리가 가장 짧은 것을 출력해라.

✏️ 계획 수립

먼저 입력의 범위를 보면 4<=n<=10000이다.
즉, 이 정도 범위면 프로그램의 실행 속도를 위해서 미리 소수를 구하는 것이 현명하다.
따라서 미리 2부터 10000까지 소수를 구한다. 이는 에라토스테네서의 체로 구한다.
그리고 이제 골드 바흐 수를 구해볼 텐데 파이썬의 딕셔너리를 하나 둔 후 브루트포스 기법으로 2부터 10000까지 두 소수의 골드 바흐 수를 전부 기록한다. 이 때 두 개 이상의 파티션이 존재할 때 가장 거리가 짧은 것으로 갱신해준다.
마지막으로 입력이 들어올 때마다 그 때의 골드바흐 수를 출력하면 된다.

💻 계획 수행

import sys


if __name__ == '__main__':
    N = 10000
    sieve = [False, False] + [True] * (N - 1)
    prime = []
    goldbach = {}
    # 10000까지의 모든 소수 찾기
    for i in range(2, N):
        if sieve[i]:
            prime.append(i)
            for j in range(i + i, N + 1, i):
                sieve[j] = False

    for i in prime:
        for j in prime:
            gold_num = i + j
            if gold_num in goldbach.keys():
                if abs(goldbach[gold_num][0] - goldbach[gold_num][1]) > abs(i - j):
                    goldbach[gold_num] = (i, j)
            else:
                goldbach[gold_num] = (i, j)

    T = int(sys.stdin.readline().rstrip())

    for _ in range(T):
        num = int(sys.stdin.readline().rstrip())
        print("{0} {1}".format(goldbach[num][0], goldbach[num][1]))

🤔 회고

이 문제는 에라토스테네서의 체를 사용하여 시간복잡도를 줄이고 브루트포스를 사용하는데 거기서도 시간 복잡도를 최대한 줄여야지 풀 수 있는 문제였다. c++이었다면 조금 더 수월했겠지만 파이썬이어서 조금 더 최적화가 필요했던 문제였다.