[백준 알고리즘] 9020 골드바흐의 추측 C++

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

9020번: 골드바흐의 추측

풀이 방법 : 

단계 1) 해당 수의 제곱근까지만 나누어보는 것 && 에라토스테네스의 체 (1929 소수 구하기와 동일)

 

에라토스테네스의 체를 사용해야 하는 이유는 시간초과 때문이다. 소수를 판별하기 위해서 이전의 수를 모두 나누어보는 것은 시간복잡도가 엄청나게 커지는 방법이기 때문이다. 

 

 

해당 수의 제곱근까지만 나누어보는 것:

쉽게 생각해보자. 예를 들어 18의 소수를 구하려고 한다. 1,2,3,4,5,6,7,8,...,18 -> 루트 18은 대략 4. xx이다.

만약 4(루트 18) 보다 큰 소인수가 있다면 이미 그 짝은 4보다 작은 수일 것이다. ex) (4보다 큰 소인수 == 6 )-> (6의 짝 == 3)

그러니 이미 순차적으로 i를 증가시키는 동안 이미 4보다 작은 수로(3으로) 나누어보았을 것이다.

 

 

에라토스테네스의 체:

이름부터 어려운 에라토스테네스...의 체... 원리는 easy하다. 이전에 든 예 18로 계속 진행을 해보겠다.

1,2,3,4,5,6,7,8,...,18 에서 일단 소수가 될 수 없는 1을 빼고, 다음 수인 2가 소수인지 판별한다.

2가 소수네 ? --> 2를 제외한 2의 배수 다 삭제 : 2,3,5,7,9,11,13,15,17

2 다음 수인 3이 소수인지 판별한다. 

3이 소수네 ? --> 3을 제외한 3의 배수 다 삭제 : 2,5,7,11,13,17

~~ 해서 18일 때까지 반복을 하면 된다.

 

단계 2)  (입력된 수 /2 - i )+ (입력된 수 /2 + i ) = 입력된 수 이용하기

이런 문제를 만나면 예시 몇 개를 노트에 끄적여 본다. 

18 -> 1,17 / 2, 16 / 3, 15 / ... 7,11 / 8,10 / 9,9

처음에는 (입력된 수 /2)의 가장 큰 소수, 그리고 입력된 수 - {(입력된 수 /2)의 가장 큰 소수} 가 소수인가 아닌가.. 이렇게 말로 들어도 복잡한 식을 작성하려고 했다.. 하지만 백준 문제를 풀면서 구현보다 중요한게 알고리즘의 싸움이라는 것을 깨달았기 때문에 조금 더 고민해보았다.

그래서 도출된 결론이 바로 " (입력된 수 /2 - i )+ (입력된 수 /2 + i ) = 입력된 수 " 를 이용하는 것이다.

뚫어지게 쳐다보면 9,9 -> 8,10 -> 7,11 처럼 중간의 수에서 0부터 1씩 빼지는 관계임을 알 수 있다. 중간에서 시작하는 이유는 문제에서 "만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다."라는 제약사항을 추가했기 때문이다.

 

(입력된 수 /2 - i )와 (입력된 수 /2 + i ) 모두가 소수일 경우 출력 그리고, break를 걸어 for문을 뛰쳐 나온다.

 

작성한 코드는 다음과 같다.

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    int count;
    cin >> count;
    
    //    1. 에라토스테네의 체
    int array[10001];
    for(int i = 0 ; i< 10001 ; i++){
        array[i] = 1;
    }
    array[0] = 0;
    array[1] = 0;
    for(int i = 2; i< sqrt(10001); i++){
        if(array[i] == 1){
            for(int j = i*i; j< 10001 ; j = j+i){
                array[j] = 0;
            }
        }
    }
    
    //    2. M 입력을 받은 후 M/2-i 와 M/2+i 둘 다 소수인 것 찾기
    int M;
    for(int k = 0 ; k< count ; k++){
        cin >> M;
        int i = 0;
        while(1){
            if(array[M/2-i] != 0 && array[M/2+i] != 0){
                cout <<M/2-i<<" "<<M/2+i<<"\n";
                break;
            }
            i++;
        }
    }
    return 0;
}

성공한 사진 !