eff3ct's st0rage Dev Blog

[백준 BOJ] 6588. 골드바흐의 추측

10 Aug 2021

난이도

Silver I

문제 풀이

테스트 케이스에 대해 골드바흐의 추측을 검증하는 문제이다. 그래서 주어지는 짝수 정수 n보다 작은 소수들을 모두 다 알아야할 필요가 있다. n의 최대값은 1,000,000이니, 백만까지의 소수들을 구하자.

소수들을 구하는데에는 ‘에라토스테네스의 체(Eratosthenes’s Seive)’라는 알고리즘이 사용된다. 에라토스테네스의 체는 n이하의 수들에서 소수를 얻어내는데 사용되는데, 아이디어는 간단하다. 먼저 가장 작은 소수인 2부터 시작해서 그 배수들을 전부 다 지워낸다. 모든 배수를 다 지워냈으면, 그 다음으로 작은 소수를 택해 그 소수의 배수들을 모두 지운다. 이렇게 계속 반복하면 남는것은 필연적으로 소수이게 된다. 이를 코드로 짜면 다음과 같다.

//eratosthenes's sieve
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i <= 1000; ++i) {
        if(isPrime[i]) {
            for(int j = i * i; j <= 1000000; j += i) {
                isPrime[j] = false;
            }
        }
    }

isPrime이라는 bool형 배열을 만들고, 그 배열에 소수인지 아닌지를 표시한다.(기본 설정값은 모두 true)

0과 1은 소수가 아니므로 제외해주고 2부터 시작해서 배수들을 지워준다. 이때 \(\small \sqrt{n}\)까지만 이 과정을 수행해도 모든 소수를 구할 수 있다. 따라서, \(\small\sqrt{n} = 1000\) 까지만 반복문을 돌고, 그 배수들을 지워준다. 이때, 안쪽 루프는 \(\small i^{2}\)부터 시작하는데, 그 이유는 \(\small (i - 1) \cdot i\)처럼 \(\small i^{2}\)보다 작은 배수들은 이전에 이미 지워지기 때문이다. 그래서 \(\small i^{2}\)부터 돌도록 최적화해줄 수 있다. 이렇게 코드를 짜면, 시간복잡도는 \(\small O(nlog(logn))\)이라고 한다. \(\small log(logn)\)이 굉장히 느리게 증가하기 때문에 사실상(n이 매우매우 큰수가 아니면) \(\small O(n)\)과 거의 같은 시간복잡도이다.

//save prime numbers
    vector<int> primeVector;
    for(int i = 3; i <= 1000000; ++i) {
        if(isPrime[i]) primeVector.push_back(i);
    }

그렇게 소수들을 찾고 그 소수들을 primeVector에 모두 넣어주었다. (이때, 2는 제외하도록 한다.)

소수들을 찾았으면, 그 소수들로 어떻게 해야 b - a가 최대가 되면서 n = a + b꼴로 출력할 수 있는지 생각해보아야 한다.

가장 간단한 방법은 n보다 작은 모든 소수들을 돌아보며 a + b = n이 되는지 체크하고 b - a가 최대가 되는 때를 저장하는것이다.

void solve(int& n, vector<int>& primeVector) {
    int a = 0, b = 0;
    int lb = lower_bound(primeVector.begin(), primeVector.end(), n) - primeVector.begin();
    for(int i = 0; i < lb; ++i) {
        for(int j = i; j < lb; ++j) {
            if((primeVector[i] + primeVector[j] == n) && (primeVector[j] - primeVector[i]) >= (b - a)) {
                a = primeVector[i];
                b = primeVector[j];
            }
        }
    }
    cout << n << " = " << a << " + " << b << '\n';
}

이렇게 짜면, 분명 숫자는 찾아진다. 그러나, \(\small O(n^{2})\)이라 TLE를 받게된다. 백만까지의 소수 개수는 78000개 정도이다. 그래서 TLE를 받게 된다. 그렇다면 \(\small O(n^{2})\)보다 작은 복잡도를 가지는 방법을 생각해보아야한다. n보다 작은 소수들 중 가장 큰 소수와 가장 작은 소수부터 시작해서 범위를 줄여가며 체크를 하면 되지 않을까? a b c d e(오름차순) 이 n보다 작은 소수들이라고 해보자. 먼저 a + e부터 시작한다. a + e > n이면 e를 줄이면 되니 e보다 작은 d로 체크를 해주면 된다. 만약 a + e < n이면 a를 크게해주면 되니 a보다 큰 b로 체크를 해주면 된다. 이걸 반복해 n이 되면 그때가 차이가 최대인 소수들이 될거니 분명 위의 \(\small O(n^{2})\)방법보다는 빠르게 될 것이다. 아래는 이 방법을 구현해본 것이다.

void solve(int& n, vector<int>& primeVector) {
    int lb = lower_bound(primeVector.begin(), primeVector.end(), n) - primeVector.begin() - 1;
    int a = 0, b = lb;
    int nowSum = 0;
    while(true) {
        nowSum = primeVector[a] + primeVector[b];
        if(nowSum == n) break;
        else if(nowSum > n) b--;
        else if(nowSum < n) {
            a++;
            b = lb;
        }
    }

    cout << n << " = " << primeVector[a] << " + " << primeVector[b] << '\n';
}

근데, 이것보다 더 좋은 방법이 있다. primeVector[a] + primeVector[b] == n인지 체크하는 방법 대신 primeVector[b] == n - primeVector[a]임을 이용해보자. n에서 primeVector[a]값을 뺀 값이 소수라면 그게 primeVector[b]가 되지 않겠는가? 그래서, 그걸 이용하면 상당히 간단하게 코드를 짤 수 있다.

void solve(int& n, vector<int>& primeVector) {
    int a = 0;
    
    while(true) {
        if(isPrime[n - primeVector[a]]) break;
        a++;
    }

    cout << n << " = " << primeVector[a] << " + " << n - primeVector[a] << '\n';
}

n = a + b에서 a가 결정되면 b가 결정될테니, 그것을 이용해 이렇게 짜면 자연스럽게 b - a가 최대인 쌍들이 구해진다.

식을 살짝만 변형해 구하는걸 바꾸기만 했는데 쉬워졌다. 나는 이걸 한번에 떠올리지는 못해서 위의 삽질을 열심히 했다..

여튼 구하는 것을 바꾸기만 해도 쉽게 문제를 풀어나갈 수도 있는것이다.

여담으로, 코드에 Goldbach’s conjecture is wrong을 출력하게 해놓은 부분은 없다. 왜냐하면, 이 추측이 \(\small 10^{18}\)까지는 성립한다고 밝혀져 있어서 \(\small 10^{6}\)까지는 당연히 되야하니까..

코드 전문

6588 // 골드바흐의 추측

Related posts