[백준]_9020번 : 골드바흐의 추측(파이썬 and C언어)

9020번: 골드바흐의 추측

논리 과정을 세우는 데는 그다지 어렵지 않았는데 막상 소수 판별을 하는 부분에서 시간 초과가 계속 났던 문제이다. 또한 이 문제에서 가장 까다로운 조건인  "만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다"을 어떻게 해결하는지도 골머리였다.

---

전략

다행히 n은 4 이상 10000 이하이기 때문에 10000 이하의 소수들을 먼저 배열에 저장해 주고 나중에 돌아와서 '이 숫자가 소수인가?=이 숫자가 이 배열 안에 있나?'와 같이 소수를 다루는 방법이 있을 것이다. 아니면 숫자를 소수판별 함수에게 넘겨 그것이 소수이면 1을 반환하고 아니면 0을 반환하게 할 수도 있다.

 

두가지 방법을 모두 해볼 것이긴 한데 두 전략 공통적으로 에라토스테네스의 체를 사용할 것이다.  소수를 코딩으로 많이 구현해보지 않은 사람몇 달 전의 me..들은 소수 판별을 위해 반복문을 작성할 때 나누는 숫자를 n-1까지 설정하기 십상이다. 하지만 에라토스테네스의 체를 사용하면 n이 소수임을 알기 위해서는 sqrt(n)까지만 확인해 주면 된다. 왜냐하면 (sqrt(n))^2=n이기 때문에 sqrt(n) 보다 큰 숫자를 이용해 n으로 나누어 떨어지는지 검사할 필요가 없다. 

 

시도 1(Python)

import sys
input=sys.stdin.readline
prime=[2,3]
for i in range(3,10001):
    for j in range(2,int(i**(0.5))+1):
        if not i%j: break
        elif j==int(i**(0.5)): prime.append(i)
for _ in range(int(input())):
    gold=int(input())
    save=0
    for num in prime:
        if num>gold//2: # 문제에 의하면 gold는 반드시 짝수이기 때문에 그냥 gold//2라고 써도 무방
            break
        elif gold-num in prime:
            save=num
    print(f"{save} {gold-save}")

<평가> Python3에서는 안돌아가고 PyPy3에서는 잘만 돌아가는데 prime 리스트를 채우는 데에 시간이 너무 오래 걸린다. 또한 num in prime 같이 in 연산자는 선형적으로 원소를 탐색하기 때문에 리스트의 길이가 길수록 연산시간이 늘어난다. 따라서 이 전략 대신 숫자를 받고 그 숫자가 소수인지 아닌지만 판별해 주는 함수를 만들어서 다시 시도해 보자. 또한 num을 이용해서 아래에서부터 올라와 두 소수 간의 간격을 좁히는 것이 아닌 애초에 gold//2에서부터 시작해 내려오는 전략이 훨씬 빠르다.

 

수정

import sys
input=sys.stdin.readline
def isitprime(n):
    for i in range(2,int(n**(0.5))+1):
        if not n%i: return 0
    return 1
for _ in range(int(input())):
    gold=int(input())
    tail, head = gold//2,gold//2
    while 1:
        if isitprime(tail) and isitprime(head):
            print(tail, head)
            break
        tail-=1
        head+=1

 무려 1144ms(PyPy3) 에서 176ms(Python)으로나 줄였다!!

시도 2(C언어)

#include <stdio.h>
#include <math.h>
int isitprime(int num){
    for(int i=2;i<int(sqrt(num))+1;i++){
        if(num%i==0) return 0;
    }
    return 1;
}
int main() {
    int user, gold;
    scanf("%d",&user);
    for(int k=0;k<user;k++){
        scanf("%d",&gold);
        int tail=gold/2, head=gold/2;
        while(1){
            if((isitprime(tail)) && (isitprime(head))){
                printf("%d %d\n",tail,head);
                break;
            }
            tail-=1;
            head+=1;	
        }
    }
    return 0;
}