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

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

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 17109번 문제 - 골드바흐 파티션 에 대한 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 17103

 

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

 

17103번: 골드바흐 파티션

 

문제 해석

 

문제에서 주어지는 짝수가 두 소수의 합으로 표현이 가능한지를 알아보고

그 조합이 몇 가지가 존재하는가를 출력하는 문제입니다.

에라토스테네스의 체를 사용해서 소수 리스트를 뽑아두고 이를 활용해서 문제 풀이를 시도해봅시다.

 

풀이

 

# 에라토스테네스의 체
sieve = [True] * (1000001)
sieve[0], sieve[1] = False, False

for i in range(2, int(1000000 ** 0.5) + 1):
    if sieve[i] == True:
        for j in range(i + i, 1000001, i): # i이후 i의 배수들을 False 판정
            sieve[j] = False

# 테스트 케이스 개수
t = int(input())

for _ in range(t):
    count = 0
    n = int(input())

    for i in range(2, n // 2 + 1): # 순서가  다르지만 조합이 같은 경우를 제외하는 범위
        if sieve[i] and sieve[n-i]:
            count += 1
    
    print(count)

 

풀이 해석 및 팁

 

우선 문제에서 주어지는 자연수 N의 범위는 1000000까지 이므로 에라토스테네스의 체를 이용해

1000000개의 리스트 요소에 소수인지 아닌지를 채워줍니다.

위에서 만든 리스트를 활용해 for 문을 돌립니다.

sieve 리스트의 인덱스는 실제 숫자와 그대로 매칭이되며 인덱스가 2이면 소수이므로 True가 들어있고

4이면 소수가 아니므로 False가 들어있습니다.

따라서 sieve[i] 와 sieve[n-i]가 둘다 소수라면 i + (n-i) = n 이므로 n은 소수의 합으로 구성이 가능한 수가 됩니다.

이렇게 count를 1씩 증가시켜서 최종적으로 몇개의 조합이 존재하는가를 출력하면 문제가 해결됩니다.

---

여기까지 백준 17103 번 - 골드바흐 파티션의 풀이였습니다.

 

에라토스테네스의 체는 소수 관련된 문제에서 정말 유용하게 잘 쓰이네요.

 

두 소수의 합을 구성할 때 앞뒤만 다르고 수의 조합이 같은 경우를 제외하기위해

 

for문의 범위를 n//2 + 1로 처리해주는 재치를 발휘할 수 있는 문제였습니다.

 

재치있는 방법을 생각하면서 코드를 짜려고 노력하는 습관을 들여봅시다.

 

감사합니다.