[Baekjoon] 17103 - 골드바흐 파티션 (Python)

문제

[BaekJoon] 17103 골드바흐 파티션

1차 시도

“두 소수의 순서만 다른 것은 같은 파티션이다.”

즉, N이 8일 때 (3, 5), (5, 3)은 같은 파티션 이라는 것인데,,

왜 그렇게 생각했는지 모르겠지만 당연히 중복도 안된다고 생각하고 문제를 풀었다.

그래서 combinations으로 소수 리스트에서 2개의 수를 뽑아서 더했을 때 n과 같으면 된다고 생각했다.

예제출력을 보면 N이 10일 때 골드바흐 파티션의 수는 2이다.

하지만 내가 이해한대로, 내가 코드 짠 대로는 10일 때 골드바흐 파티션의 수는 1이다.

(3, 7) 이것말고는 도저히 보이지가 않는데 왜 2개일까 하고 생각해봤다,,

(5, 5) 해서 2개이다!

“어떤 수에 대해, 그 수를 두 소수의 합으로 표현하는 방법의 경우의 수를 그 수의 골드바흐 수라고 부른다”

두 소수의 합이면 (5, 5)는 소수 1개로 나타낸 거 아냐,,?

근데 내가 이해를 잘 했다고 하더라도 이 코드는 시간초과, 메모리초과가 났을 것이다.

import sys
from itertools import combinations
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    primes = []
    n = int(input())
    for i in range(2, n+1):
        for j in range(2, int(i**0.5)+1):
            if i % j == 0:
                break
        else:
            primes.append(i)
    cnt = 0
    for i in list(combinations(primes, 2)):
        if sum(i) == n:
            cnt += 1
    
    print(cnt)

2차 시도

list를 미리 선언해주고 똑같이 에라토스테네스의 체를 사용해서 미리 소수가 아닌 수들을 제거한다.

이렇게 하면 소수만 1로 나타내는 배열이 될 것이고

i와 n-i이 소수이면서 동시에 i와 n-i의 합이 n이 되는 갯수를 카운팅하면 된다.

import sys
input = sys.stdin.readline

arr = [1] * 1000001
arr[0], arr[1] = 0, 0

for i in range(2, 1000001):
    if arr[i]:
        for j in range(i*2, 1000001, i):
            arr[j] = 0
            
T = int(input())

for _ in range(T):
    cnt = 0
    n = int(input())
    for i in range(2, n//2+1):
        if arr[i] and arr[n-i]:
            cnt += 1
    print(cnt)