크래프톤정글 6주차; TIL - 백준 9020 골드바흐의 추측 재도전

2022-12-04

백준 9020 골드바흐의 추측 파이썬

참고:

무엇?

시간 초과의 굴레에서 벗어날 수 없었던 골드바흐의 추측 문제를 다시 풀고 이해하기

왜?

첫 달에 어려웠거나 한 번에 풀지 못한 문제 다시 푸는 중

어떻게?

• 시간 초과에서 벗어나는 방법

1. 소수 리스트를 만들기
   1. n의 범위인 10000까지 소수를 미리 구한다
      • 나는 테스트 케이스를 받을 때마다 소수를 일일이 새로 구했다. → 시간 초과 확률↑
      • 알고리즘 문제를 많이 풀어보지 않아서인지 어쩐지는 몰라도, 10000까지 미리 다 찾는게 마음에 들지 않았다! 그래서 미리 다 구하지 않는 다른 방법은 없을까 고민하다가 다른 정글메이트(?)에게 물어봤더니, DP의 memoization 기법처럼 이전 테스트 케이스의 이미 구한 소수를 저장하는 방식을 얘기해줬다. 구현해보진 않았지만 좋은 생각인 듯.
   2. n의 소수를 구할 때, 까지의 숫자만 탐색하면 된다.
      • 난 1부터 n까지 다 구했다. → 시간 초과 확률↑
      • 곰곰이 생각해보면 당연한 이치.
   3. 하나의 소수 i를 찾으면, i의 배수는 모조리 소수에서 제외시킨다.
2. 골드바흐 수를 탐색하기
   1. 탐색을 시작하는 수를 n의 중간값으로 지정한다.
      • 반반 나눠 동시에 탐색하므로 O(n)안에 끝낼 수 있음.
      • 나는 1부터 n까지 모든 경우의 수를 다 탐색하는 방법으로 했기 때문에 O(n^2) → 시간 초과 확률 ↑
   2. 탐색을 위한 인덱스 a, b를 지정하고 중간값에서 시작해 각각 1씩 감소, 1씩 증가 시켜가며 소수 조건, 합이 n이 되는 조건을 확인한다. 가장 차이가 적은 값부터 탐색하게 된다.

# https://www.acmicpc.net/problem/9020
# 골드바흐의 추측: 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있음 -> 골드바흐의 수 
# 골드바흐 파티션: 두 짝수를 두 소수의 합으로 나타낸 것
# 2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력
# 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

import sys

sieve = [True] * 10000
# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
m = int(100000 ** 0.5)
for i in range(2, m + 1):
    if sieve[i] == True:           # i가 소수인 경우
        for j in range(i+i, 10000, i): # i이후 i의 배수들은 소수가 아니므로 False 판정
            sieve[j] = False

T = int(sys.stdin.readline()) 
for _ in range(T):
    n = int(sys.stdin.readline())
    mid = n // 2     # 탐색을 위한 중간값 지정
    # 소수 리스트를 검색하기 위한 인덱스 a, b로, 
    # a는 1씩 감소, b는 1씩 증가시켜 가장 차이가 적은 값부터 찾게 됨
    a, b = mid, mid  
    for _ in range(mid):
        if (sieve[a] and sieve[b]) and (a + b == n):  # 소수이고 합이 답과 같은 경우
            print(a, b)   
            break
        else:
            a -= 1
            b += 1