[백준] 17103: 골드바흐 파티션

이번 문제는 백준 난이도 실버 2인 '골드바흐 파티션' 문제이다.

https://www.acmicpc.net/problem/17103

 

 

이 문제는 골드바흐 추측에 따라 어떤 짝수가 입력됐을 때, 그 짝수의 골드바흐 파티션 갯수를 구하는 문제다.

 

골드바흐 파티션이란?

: 골드바흐 추측에 따르면 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다는 것이다.

즉, 어떤 짝수.  예로 4가 주어졌을 때,

이 4는 4이하의 소수 (2, 3)중에서 두 개의 소수를 가지는 쌍의 합으로 4를 표현할 수 있다는 의미다.

→ 여기서 포인트! 동일한 소수의 쌍으로도 가능하다는 점이다.  2+2 = 4 이런식으로 말이다.

 

6이라면 (2, 3, 5) 중 3 + 3 = 6을 만들 수 있고,

10이라면 (2, 3, 5, 7) 중 3 + 7 = 10, 5 + 5 = 10을 만들 수 있다.

여기서 두 소수의 쌍이 골드바흐 파티션이다.

 

개념은 이 정도로 하면 충분할 거고,

문제의 조건 중에 소수의 순서만 다른 파티션은 같은 파티션으로 간주한다.

이 말은 즉 (3, 7)과 (7,3)은 같은 쌍으로 보며 2개가 아닌 1개의 파티션으로 간주한다는 것이다.

 

이 조건에 따라 우리는 하나의 규칙을 만들 수 있다.

 

파티션에서 소수의 순서가 바뀌는 순간은 첫번째 소수가 두번째 소수보다 커지는 경우이다.

그래서! 첫번째 소수가 두번째 소수보다 커지기 전까지만 반복해서 찾아주면 된다!!

 

바로 코드로 넘어가보자.

 

---

 

[Python]

 

T = int(input())

inputs = [int(input()) for _ in range(T)]
max_num = max(inputs)

 

우선 입력 조건에 맞게 T만큼의 숫자를 입력하고 리스트에 저장해준다.

그리고 입력값의 최댓값을 찾아 max_num 변수에 저장한다.

→ 최댓값 저장한 이유는 밑에서 바로 알 수 있다.

 

is_prime = [True] * (max_num+1)
is_prime[0] = is_prime[1] = False
    
for i in range(2, int(max_num**0.5) + 1):
    if is_prime[i]:
        for j in range(i*i, max_num+1, i):
            is_prime[j] = False

 

소수를 찾기 위해선 우리가 이전에 썼던 '에라토스테네스의 체'를 이용하면 구할 수 있다.

입력 조건에서 짝수의 최댓값은 1,000,000이다.

하지만 1,000,000크기의 리스트를 바로 만들지 않고 우리는 입력한 값에서 최댓값을 찾아 그만큼의 크기로 만들어 주겠다.

→ 최대한 효율적으로!

 

이렇게 체를 이용해 소수만을 걸러낸 리스트를 생성했다.

 

이제 우리는 이 리스트를 통해 입력된 짝수 중 골드바흐 파티션을 찾아내면 된다.

 

for num in inputs:
    count = 0
    for i in range(2, num//2+1):
        if is_prime[i] and is_prime[num-i]:
            count += 1
    result.append(count)

 

우선 파티션 갯수를 세어줄 count 변수를 생성한다.

그 후 아까 말했던 규칙인 첫번째 소수가 두번째 소수보다 커지기 전까지만 반복을 진행한다.

그리고 여기서 조건으로 파티션 판단을 할 수 있는데

원래 소수 + 소수를 해서 이 값이 입력한 짝수와 같은지 판단을 해주어야 한다.

Ex) 10 → 3 + 7  합이 10이 맞는지.

 

그렇지만 우리는 이미 체를 만들어두었고, 입력한 짝수가 주어지고 2부터 1씩 증가하며 순회하기 때문에

num   =    i + (num - i)로도 표현할 수 있다.

즉, 이렇게 하면 무조건 두수의 합이 num이 되는 쌍에 대해서만 조건 검사를 하며

체를 통해 그 두 수들이 소수인지만 판단해주면 골드바흐 파티션인지 구할 수 있는 것이다.

 

<전체코드>

T = int(input())

inputs = [int(input()) for _ in range(T)]

max_num = max(inputs)

is_prime = [True] * (max_num+1)
is_prime[0] = is_prime[1] = False
    
for i in range(2, int(max_num**0.5) + 1):
    if is_prime[i]:
        for j in range(i*i, max_num+1, i):
            is_prime[j] = False


result = []

for num in inputs:
    count = 0
    for i in range(2, num//2+1):
        if is_prime[i] and is_prime[num-i]:
            count += 1
    result.append(count)

for i in range(len(result)):
    print(result[i])

 

결과를 보면

 

 

예제의 결과와 동일하게 잘 나오는 걸 볼 수 있다.