[백준/C++] 골드바흐흑흙의 추측 (No. 32647)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

A, B사이의 소수들의 합으로 K라는 수를 만들 수 있는지 라는 문제를 보고 처음에 단순히 경우의 수를 계산하면 안되겠다는 생각이 들었다.

 

B-A<301 이라는 조건에서 가장 소수가 많은 구간인 2~302 구간을 살펴보면 소수가 62개로 2^62가 되기 때문이다.

 

하지만, 모든 경우를 직접 계산하지 않고 소수의 합을 Memoization으로 몇 번 나왔는지 계산하면 중복되는 경우가 생기므로 빠르게 계산할 수 있겠다는 생각이 들었다.

 

예를 들어 2, 3, 5, 7의 소수가 있을 때를 아래 그림을 통해 생각해보자.

 

fig1

 

 

이렇게 덧셈을 해가며 계산하면 중복되는 경우가 생긴다.

5의 경우 소수 5만 사용하는 경우와 2, 3을 더해 5를 만드는 경우 2개다.

 

이를 기록해 중복되는 경우를 줄이고 개수를 파악하면 빠르게 문제를 해결할 수 있게 된다.

 

이제 A와 B사이의 소수를 구하는 방법을 생각해보자.

 

에라토스테네스의 체를 이용해 A와 B사이의 소수를 구하는 방법도 있다.

또한 A와 B의 차가 300이하이므로 300*sqrt(B)번 연산해서 A~B사이의 수가 소수인지 판단하는 방법도 있다.

 

sqrt(B)번 연산하는 방법은 B가 소수가 아니라면 2~sqrt(B)사이의 수에서 B를 나누는 약수가 적어도 하나 있기 때문에 이를 이용하는 방법이다.

 

이렇게 소수를 구한 다음 위의 Memoization을 이용해 K를 만들 수 있는 조합을 계산하면 된다.

 

+ 실제로 궁금해서 범위를 1~301 까지로 했을 경우 몇 번의 연산을 하게 되는지 예측해보고 계산해봤다.

 

1~301 사이의 소수를 전부 더하면 8275이다.

 

그러면 소수의 합으로 나타낼 수 있는 수가 8275개 보다 작다는 사실은 자명한 사실이다.

왜냐하면 모든 소수의 합이 8275이므로 소수의 합은 2~8275사이에 전부 존재하기 때문

 

그러면 소수의 개수가 약 62개이므로 최대 8275*62번의 연산을 해도 약 50만번 연산하게 된다는 결론이 나온다.

실제로 계산할 때마다 Count를 세본 결과 296303으로 50만보다 작게 나왔다.

 

추가로 K보다 큰 경우를 가지치하면 더 연산 횟수를 줄일 수도 있을 것이다.

 

 

[아이디어 정리]

1. A~B 사이의 소수들을 구한다.
2. Memoization을 이용해 소수의 합으로 만들 수 있는 수들을 계산하고 그 수를 만들 수 있는 조합의 경우를 저장한다.
3. 최종적으로 K를 만들 수 있는 경우의 수를 구해 출력한다. 

 

 

Code

 

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
using namespace std;

struct cmp
{
    bool operator ()(const long long& a, const long long& b) const
    {
        return a > b;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    long long A, B, K;
    cin >> A >> B >> K;
    vector<long long> primes(0);
    for (int i=B; i>=A; i--)
    {
        bool flag = true;
        for (int j=2; j<= sqrtl(i); j++)
        {
            if (i%j==0)
            {
                flag = false;
                break;
            }
        }
        if (i == 1) {
            continue;
        }
        if (flag)
        {
            primes.push_back(i);
        }
    }
    map<long long, long long, cmp> m;
    m[0] = 1;
    long long cc;
    long long calc = 0;
    for (int i=0; i<primes.size(); i++)
    {
        for (map<long long, long long, cmp>::iterator it=m.begin(); it!=m.end(); it++)
        {
            calc += 1;
            cc = it->first + primes[i];
            if (cc<=K)
                m[cc] += it->second;
        }
    }
    cout << m[K] << endl;
    return 0;
}

---

 

그냥 생각없이 Nlog(N)의 시간이 걸리는 에라토스테네스의 체를 사용했는데 느려서 다른 사람의 방법을 보니 A와 B의 차이가 적기 때문에 그냥 소수인지 판단하는 방법을 사용하는 걸 보고 수정했다.

 

예전에도 이 문제처럼 상한이 정해져있어서 실제 시간복잡도가 적은 문제들이 있었다.

이 문제도 마찬가지로 1~301사이의 소수를 계산해보니 상한이 있어서 중복을 제거하면 2^62의 시간이 아닌 더 적은 시간이 걸리는 문제였다.

 

문제 자체는 쉽게 풀었지만 풀이에 대한 이유를 생각하면 생각보다 어렵고 좋은 문제였던 것 같다.

 

https://www.acmicpc.net/problem/32647