1. 문제

출처: 백준 9020번 골드바흐의 추측

2. 풀이

제한에 적혀있는 범위까지 미리 소수를 구해둔다. (에라토스테네스의 체를 활용)

백준 1929번, 소수구하기 풀이 에서 해당 원리 설명을 확인해볼 수 있다.

그다음, 작은 소수부터 주어진 숫자까지 가능한 골드바흐 파티션이 있는지 확인한다.
이때, 문제가 되었던 건 "소수와 주어진 숫자의 차이"도 소수인지 확인하는 부분이었다.

count를 이용하여 확인하고자 했을 때에는 시간 초과가 발생하였다.
"O(n)의 시간 복잡도"를 가지기 때문으로 추측된다.

따라서, 생성해놓은 에라토스테네스의 체를 활용하여 소수를 판별하는 것이 좋다.

3. 소스코드

max_n = 10000
s = [False,False] + [True]*(max_n-1)
prime = []

for i in range(2,max_n+1):
    if s[i]:
        prime.append(i)
        for j in range(2*i,max_n+1,i):
            s[j] = False

T = int(input())

for _ in range(T):
    n = int(input())
    diff_prime = n
    candidate = []
    for i in range(len(prime)):
        diff = n - prime[i]
        if diff < prime[i]:
            break
        elif s[diff] == True:
            if diff_prime > diff - prime[i]:
                candidate = [prime[i], diff]
                diff_prime = diff - prime[i]
    print(*candidate, sep = " ")

4. 그 외

처음에 문제를 접했을 때에는, 시간 초과가 계속 발생해서 꽤나 애를 먹었던 기억이 난다.
본격적으로 시간 초과에 관해 고민하게 되는 순간이었다.
당시에는 다른 분들의 풀이를 보지 않았다면, 떠올리지 못했을 것 같다.