[C++] 백준 9020 - 골드바흐의 추측

• 풀이 방법

• 초기 코드 (시간초과)

• 최종 코드

난이도 : 실버 2

 

 

풀이 방법

첫번째로 생각한 방법은 입력크기를 고려하여 10000까지의 소수를 구하고, 그 후 입력값에 동일한 두 값의 덧셈을 구하려고 했다.

소수를 구하는 코드는 구구단처럼 2단부터 시작해서 10000단까지 10000이하인 수는 arr[n] = 1로 처리했다.
예를 들면 2x3=6은 소수가 아니기 때문에 arr[6] = 1 으로 처리.

따라서 arr[n] = 0 인 n은 소수가 된다.

그 후 2부터 입력된 값까지 소수 덧셈의 모든 경우의 수 중에서 두 수의 차가 가장 적은 것을 출력했다.

 

초기 코드 (시간초과)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;

int T;
int arr[10001];

int main(void){
    scanf("%d", &T);
    
    for(int i=0; i<T; i++){
        int input = 0;
        int diff = INT_MAX;
        int X = 0, Y = 0;
        
        scanf("%d", &input);
        for(int i=2; i<=input; i++){
            for(int j=2*i; j<=input; j+=i){
                arr[j] = 1;
            }
        }
        
        for(int i=2; i<=input; i++){
            if(arr[i] == 0){
                for(int j=i; j<=input; j++){
                    if(arr[j] == 0){
                        if(input<i+j)
                            break;
                        if(input == i + j){
                            int tmp = j - i;
                            if(tmp < diff){
                                diff = tmp;
                                X = i;
                                Y = j;
                            }
                        }
                    }
                }
            }
        }
        printf("%d %d\n", X, Y);
    }
}

일단 굉장히 지저분한 if문이 눈에 띈다.
성공도 하지 못했다. 시간초과가 발생하였다.
어느 부분에서 시간을 줄일지 고민했다.
먼저 소수를 구하는 코드는 저 방법이 최선이라고 생각했다.

결국 입력 값에 대한 두 수의 덧셈을 어떻게 구현하냐가 핵심이다.

문제에서 입력 값은 짝수이며 두 소수의 덧셈이 해당 입력 값이 되는 경우가 무조건 존재한다. 또한, 문제에서 두 수의 차가 가장 적은 경우를 출력해야 했기에 심플하게 해당 짝수를 2로 나눈 두 수부터 소수인지 검사하는 코드를 작성했다. 소수가 아니라면 해당 수를 +1, -1해서 가장 효율적으로 찾을 수 있게 작성했다.

 

최종 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;

int T;
int arr[10001];

int main(void){
    scanf("%d", &T);
    
    for(int i=0; i<T; i++){
        int input = 0;
        int diff = INT_MAX;
        int X = 0, Y = 0;
        
        scanf("%d", &input);
        for(int i=2; i<=input; i++){
            for(int j=2*i; j<=input; j+=i){
                arr[j] = 1;
            }
        }
        
        int tmp1 = input/2;
        int tmp2 = input/2;
        
        
        while (X == 0 && Y == 0) {
            
            if(arr[tmp1] == 0 && arr[tmp2] == 0){
                X = tmp1;
                Y = tmp2;
            }else{
                tmp1++;
                tmp2--;
            }
        }
        
        printf("%d %d\n", Y, X);
    }
}