[BOJ 9020]골드바흐의 추측

9020번: 골드바흐의 추측

문제 분석

• 시간제한 2초 : 2억 연산 (Big-O 기준)
• 어떤 짝수X가 입력되면 X보다 작은 소수를 구해 두 소수의 합이 X가 되는 경우를 구한다.
• 그 경우가 여러 경우일때, 두 소수의 차가 가장 작은 경우를 구한다.

풀이 방식

• 처음엔 규칙을 구해 그 규칙을 코드로 바꿔보려 했지만, 규칙을 찾지 못했다.
  (검색해보니 저명한 수학자들도 그 규칙은 찾지 못했다...)
• 짝수 X 보다 작은 모든 소수를 구한다. ( 에라토스테네스의 체 : https://genius00hwan.tistory.com/74 )
• i를 X/2 부터(차가 가장작은 경우) 1씩 감소 시켜 가며 i와 X-i가 소수인지 확인하는 걸 반복한다.
• 소수인 i 와 X-i 를 발견하면 출력하고 반복문을 종료시킨다.

[BOJ 4948]베르트랑 공준

#include <iostream>
#include <cmath>

#define MAX 10001

using namespace std;

int n,last, t;
bool isNPrime[MAX]; //false로 초기화

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>t;
    while(t--){
        cin>>n;
        last = n;
        for(int i=2;i<=sqrt(last);i++){ //에라토스테네스의 체
            for(int j=i;i*j<=last;j++){
                isNPrime[i*j] = true; // 소수가 아니면 true
            }
        }
        for (int i = n/2; i >= 2; i--) { // 차가 가장 작은 경우 부터 반복
            if (!isNPrime[i]&&!isNPrime[last-i]) { // 소수인 i와 X-i 를 발견하면 
                cout<<i<<" "<<last-i<<"\n"; // 출력
                break; //반복문 종료
            }
        }
    }
}

느낀 점 

• 처음에는 모든 경우의 수를 구해 차가 가장 작은 경우를 구하려 했지만 이는 비효율적이고, 시간초과가 날 것 같다는 생각이 들었다.
• 어떻게 하면 효율적일지 생각해 보니 차가 가장 작은 경우 부터 반복하면 되겠다는 생각이 들었다.
• 효율을 따져 가며 문제를 푸니 코드도 깔끔해지고 더 수행시간도 더 효율적이라는 생각이 들었다.

시간 복잡도 (각 테스트 케이스 마다)

• 에라토스테네스의 체 : O(√n * √n) = O(n)
• 소수의 합 구하기 : O(n)
  ➣ O(n)