백준 9020 : 골드바흐의 추측

이것 역시 기본 골자를 에라토스테네스의 체로 잡았다.

 

고민을 했던 부분은 for문 두개의 합이 N이 되는 것들을 찾은 다음, 그 두 수를 소수 판별하는 방법을 생각했으나

너무 오래걸릴거같다고 생각했다.

 

물론 시간복잡도까지 계산해본건 아니라 대충 그런 생각이 들어서 전에 있던 코드를 불러왔는데,

문제는 이건 단순히 소수를 구하는게 아니고 N이 되는 소수의 합을 찾아야 하는 거였다.

처음에는 단순히 하나하나 구해서 차가 가장 작은 것을 골라보려고 생각을 했으나, 막상 넣고 돌려보니 시간이 초과되었다.

 

지금 생각해보면 당연히 시간 오바가 날거같긴 했는데, 따라서 에라토스테네스의 체를 사용하더라도 '골드바흐 파티션이 여러가지인 경우 두 소수의 차이가 가장 작은 것을 출력한다' 라는 조건을 만족하면서 시간안에 해결하기 위해서는 다른 방법이 필요했다.

 

그리고 나서 생각한 방법은, for문을 돌리되 연산을 최소한으로 줄이는 것 이었다.

연산을 최소한으로 줄일 방법을 생각한 결과, 중간부터 시작해서 반복문 하나는 점점 커지고 하나는 점점 작아지는 식으로 계산하면 두 수의 차가 가장 적은 수를 구할 수 있을거라고 판단. 다음과 같이 코드를 작성하였다.

 

#include <stdio.h>

int solve() {
    int N, arr[10001], max;
    scanf("%d", &N);

    for(int i=0;i<N;i++)
        arr[i] = i;

    for(int i=2;i<=N;i++) {
        if(arr[i] == 0)
            continue;
        for(int j=i*2;j<=N;j+=i) {
            if(arr[j] % i == 0)
            arr[j] = 0;
        }
    }

    for(int i=N/2;i<=N;i++) {
        for(int j=N/2;j>=0;j--) {
            if(arr[i] + arr[j] == N) {
                printf("%d %d\n", arr[j], arr[i]);
                return 0;
            }
        }
    }

}
 
int main() {
    int test;
    scanf("%d", &test);
    for(int i=0;i<test;i++)
        solve();
    return 0; 
}

 

조금 멍청하게 짠 것 같긴 하지만 지금 내 실력으로는 이게 한계인거같아 아쉽다..