[백준][python][9020] 골드바흐의 추측

[문제]

[출처 및 링크]

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

9020번: 골드바흐의 추측

 

[어떻게 풀까?]

나는 어제 이 문제를 풀어 보았다가 실패하였다. 구현 자체는 그렇게 어렵지 않다고 생각한다. 하지만 백준에서 요구하는 시간을 초과하였고 나는 문제 풀이에 실패하였다. 왜 실패하였을까? 어떻게 해결할까? 하다가 아직 안 푼 문제중 소수 찾기라는 문제를 보게 되었다. 소수 찾기 라는 문제를 풀면서 더 효과적인 방법을 생각했고 이를 적용해 보았다. 그렇게 했더니 성공하였다. 여기서 말하는 효과적인 방법은 에라스토테네스의 체를 이용한 방법이다. 아직 안 푼 사람은 풀어보길 권장한다.

[코드]

import sys
#--------------main------------------
n = int(sys.stdin.readline())
array = [0]*(10000+1)

for i in range(2, 10000+1):
    if array[i]==0:
        j= 2
        while i*j<=10000:
            array[i*j] = 1
            j +=1

for i in range(n):
    num = int(sys.stdin.readline())
    half = num//2
    for j in range(half, 1, -1):  #절반만 실행 #큰 수 부터 진행
      if array[j] == 0 and array[num-j] == 0:
        print(j, num - j)
        break

[코드 설명]

어제는 함수를 써서 예쁘게 풀어보려고 했는데 너무 거추장스러운 것 같아서 다 지워버렸다.

일단 문제에서 요구하는 수의 범위가 10000이하의 자연수이기 때문에 나는 10000+1개의 [0]을 만들어 주었다. [0]은 소수를 판단하는 기준이 된다. (+1을 해준것은 배열이 0부터 시작해서 연산의 편의를 위해 그렇게 해주었다.)

for문을 통해서 소수만 빼고 다 [0]을 [1]로 업데이트 해 주었다. 그 아래에 있는 for문에서 num은 이 골드바흐의 추측을 진행하는 값이다. 값에 만족하는 값들을 한 번 출력해 보면 알겠지만 이 값들은 대칭적인 구조를 가지고 있기 때문에 반으로 나누어 주었다.

또한 그 간격이 가장 작은 값을 출력해야 하기 때문에 절반의 위치부터 차례대로 값을 줄여주었다.

어제는 처음부터 진행해서 그 값들을 비교 했는데 그것이 의미없는 짓임을 알았다. 처음부터 절반에서 시작해 그 값을 줄여나가게 된다면 만족하는 순간 이 값이 문제에서 요구하는 답이 된다.

값이 둘 다 [0] 즉 소수인 순간 나는 그 값들을 출력하며 break를 통해 반복문을 빠져나간다.