백준 9020번 파이썬 문제풀이(기본수학2 - 골드바흐의 추측)

 

정답 코드

import math

# 에라토스테네스의 체를 이용하여 10000까지 존재하는 소수 구해놓기
m = 10000 #문제에서 제공한 n의 범위

array1 = [True for _ in range(m + 1)] #소수를 판별(True == 소수)을 위한 리스트 선언
array1[0], array1[1] = False, False #0,1은 소수가 아니기에 False로 선언


for i in range(2, int(math.sqrt(m) + 1)): #2부터 m(10000)의 제곱근까지 반복문을 돈다.
    if array1[i]: #만약 i가 소수라면
        j = 2 #i에 곱해줄 j 선언
        while i * j <= m: #i * j 가 10000(m)이하일때까지
            array1[i * j] = False #해당 i * j 값들을 모두 소수가 아닌것으로 바꿔준다
            j += 1 #j값 증가

t = int(input()) #테스트케이스 수 입력
for _ in range(t): #테스트케이스 만큼 돈다
    n = int(input()) #골드바희의 추측을 위한 짝수 입력

    a = n // 2 #n을 2로 나누어준 몫을 대입
    b = n // 2 #n을 2로 나누어준 몫을 대입

    while True: #무한반복
        if array1[a] and array1[b]: #만약 a 와 b가 위에서 구한 리스트에 존재하는 소수라면
            print(a, b) #그 해당소수를 출력한후
            break #반복문을 빠져나온다.
        a -= 1 #a를 -1씩 줄여나가면서 체크
        b += 1 #b를 +1씩 줄여나가면서 체크

-> 이 문제에서 가장 중요한 점은 입력한 짝수를 절반으로 나누었을 때 나오는 2개의 수가 소수 라는 것이다. 예를 들어 10의 경우 5,5 가나오기 때문에 5는 소수이기 때문에 바로 정답이 된다. 

그러나 만약 그 두 수가 소수가 아닐 경우 하나는 -1씩 또다른 하나는 +1씩 늘려가면서 같은 순서에 가장 먼저 나오는 소수가 정답이라는 것이다.

예를들어 20을 절반으로 나누었을때 10,10 이나오는데 이것을 -1,+1씩 해보면 3번째에 해당하는 두 수 7,13이 정답이다.

또한 18을 절반으로 나누었을 때 9,9가 나오는데 이것을 -1,+1씩 해보면 2번째에 해당하는 두 수 7,11 이 정답이다.

 

즉, 이처럼 절반으로 나누고 동일한 간격으로 벌어져 있는 소수를 찾는것이 핵심인 문제이다. 

 

*이중 반복문과 튜플까지 써가면서 문제를 풀려고 했으나 시간초과가 계속해서 발생 했기에 이러한 규칙을 찾는 것은 노트에 적어가면서 풀며 규칙을 찾는 것이 가장 좋은 문제해결방법인거 같다.