백준 9020 [파이썬] 골드바흐의 추측 : 차집합 연산 활용

 

[Python] 백준 알고리즘 온라인 저지 9020번 : 골드바흐의 추측

 

Python3 코드

# 소수 집합 만들기
nums = {x for x in range(2, 10_001) if x == 2 or x % 2 == 1}
# nums = 2와 홀수로 이루어진 집합
for odd in range(3, 101, 2): # 101 == int(math.sqrt(10_000)) + 1
    nums -= {i for i in range(2 * odd, 10_001, odd) if i in nums}
    # 홀수의 배수로 이루어진 집합을 빼줌

# 골드바흐 수를 출력
t = int(input())
for _ in range(t):
    even = int(input())
    half = even//2  # 입력받은 짝수를 2로 나눈 몫을 구함. / 기호를 쓰면 실수가 됨.
    for x in range(half, 1, -1):  # 차이가 적은 두 수를 구하기 위해서 큰수부터 꺼냄
        if (even-x in nums) and (x in nums):  # even-x 와 x가 소수 집합에 포함 되었는지 확인
            print(x, even-x)  # 작은수부터 출력
            break

 

 

Python3 코드 풀이

1. 코드 작성에 대한 전체적인 풀이 정리

이 문제는 4보다 크거나 같은 짝수가 주어지면 보다 해당 짝수의 골드바흐 수를 출력하는 문제이다. 골드바흐 수가 여러 가지인 경우에는 가장 차이가 적은 두 수를 출력해야 한다. 이때, 2보다 큰 짝수는 두 소수의 합으로 표현할 수 있고 이러한 소수를 골드바흐의 수라고 한다.

 

2. 코드 상단부, 소수 집합을 먼저 생성한다.

nums = {x for x in range(2, 10_001) if x == 2 or x % 2 == 1}
# nums = 2와 홀수로 이루어진 집합
for odd in range(3, 101, 2): # 101 == int(math.sqrt(10_000)) + 1
    nums -= {i for i in range(2 * odd, 10_001, odd) if i in nums}
    # 홀수의 배수로 이루어진 집합을 빼줌

문제를 풀 때, 시간을 절약하기 위해서 2부터 10000까지의 숫자 중 소수로 이루어진 집합을 먼저 생성했다. 소수에는 2를 제외하고 짝수가 없기 때문에 2와 홀수로 이루어진 집합을 먼저 생성했다. 이 집합에서 소수를 판별할 때는 set자료형의 빼기 연산, 즉 차집합 연산을 활용했고 먼저 생성한 집합에서 홀수의 배수로 이루어진 집합을 빼는 방법으로 소수로 이루어진 집합을 구했다.  혹시라도 차집합 연산에 대해 필요하신 분들을 위해 이전에 작성한 포스팅을 링크해둔다. ▶파이썬 set집합 합집합,교집합,차집합

 

3. 코드 하단부, 골드바흐 수를 출력하는 코드를 작성한다.

t = int(input())
for _ in range(t):
    even = int(input())
    half = even//2  # 입력받은 짝수를 2로 나눈 몫을 구함. / 기호를 쓰면 실수가 됨.
    for x in range(half, 1, -1):  # 차이가 적은 두 수를 구하기 위해서 큰수부터 꺼냄
        if (even-x in nums) and (x in nums):  # even-x 와 x가 소수 집합에 포함 되었는지 확인
            print(x, even-x)  # 작은수부터 출력
            break

테스트 케이스 수만큼 for문을 반복하고 입력받는 짝수를 even이라는 변수에 선언하였다.

 

입력받는 수는 두 개의 정수의 합과 같다. 그래서 이 두 수를 x와 입력받은 짝수 even에서 x를 뺀 even-x로 표현했다. 예를 들어 입력받는 수가 10이라면 x의 범위는 1~5가 되고 even-x의 범위는 9~5가 된다. 여기에서 x를 구하기 위해서 먼저 입력받는 수를 2로 나눈 몫을 half라는 변수에 지정하고 1부터 half까지의 숫자 범위를 for문으로 하나씩 꺼내 변수 x에 선언하였다. 

 

골드바흐 수는 x와 even-x라는 두 정수가 모두 소수여야 한다. 그래서 if 조건식을 사용해서 x와 even-x가 위에서 생성한 소수 집합인 nums 안에 포함되는지 확인하기 위해 in 연산자를 사용하였고 두 수가 모두 소수여야 하므로 and연산자로 두 조건을 묶어주었다. 

 

4. 생각나는 대로 작성했다가 시간 초과가 났던 코드

nums = {x for x in range(2, 10_001) if x == 2 or x % 2 == 1}
# nums = 2와 홀수로 이루어진 집합
for odd in range(3, 101, 2):  # 3부터 최대값까지 홀수만
    nums -= {i for i in range(2 * odd, 10_001, odd) if i in nums}
    # 홀수의 배수로 이루어진 집합을 생성해서 빼줌

t = int(input())
for _ in range(t):
    even = int(input())
    golds = {abs(x - y): [x, y] for x in nums for y in nums if x + y == even and x <= y}
    min_gold = min(golds)
    print(golds[min_gold][0], golds[min_gold][1])

처음에 단순하게 두 개의 for문을 이용해서 소수 집합 전체에서 요소를 하나씩 꺼내는 걸 반복하면서 두 수의 합이 입력한 값과 일치하는지 여부를 확인했다. (시간이 많이 걸릴 수밖에....)

 

절댓값을 구하는 abs 함수를 이용해서 두 수의 차이를 key 값으로 하고 두 수를 value로 하는 딕셔너리를 만들어서 키 값이 가장 작은 밸류를 출력하는 방식으로 풀었다. 제대로 된 값이 출력되긴 한다..ㅎ