[C++] 백준 27519번: 소수의 합 - DP + Number Theory

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

 

1 ~ n 까지의 정수를 소수의 합으로 표현하는 방법의 개수를 구하는 문제이다.

예를 들어 8을 표현하면

1) 2 + 2 + 2 + 2

2) 2 + 3 + 3

3) 3 + 5

이렇게 3가지가 존재한다.

여기서 중요한 점은 3 + 5와 5 + 3을 같은 방법으로 고려한다는 점이다.

이는 i == 8인 경우에 dp[i] = dp[i - 3] + dp[i - 5]가 아니라는 것을 의미한다.

 

이를 위해서 우선 2만으로 만들 수 있는 숫자를 카운트한다.

dp[0] = 1로 선언해주고

dp[i] = dp[i - 2] 로 선언해주면 i == 2인 경우 dp[2] = 1을, i == 4인 경우 dp[4] == dp[2] == 1을 저장하는데,

이는 곧 4를 만들기 위해서는 우선 2만 가지고 만드는 방법이 1가지 존재한다는 것을 의미한다.

같은 케이스에서 i == 3인 경우 dp[3] == dp[1]이므로 0을 저장하고, 이는 2만 가지고는 만들 수 있는 방법이 없다는 것을 의미한다.

 

이번엔 3만으로 만들 수 있는 숫자를 카운트한다.

dp[3] = dp[3 - 3] = dp[0] = 1로 저장이 되고,

dp[6] = dp[6 - 3] = dp[3] = 1로 저장이 된다.

그러나 앞서 2만으로 만들 수 있는 방법도 존재했으니 dp[6] 은 결국 2와 3 각각으로 만들 수 있는 방법이 존재한다는 것을 알 수 있다.

 

이를 조금 확장해서 정수 6을 만들기 위해 2와 3으로 만들 수 있는 정수를 살펴보면

dp[6] = dp[4] = dp[2] = 1 을 앞서 저장한 상태이고,

dp[6] = dp[3] = 1이 추가로 들어오게되므로

dp[6] = dp[6] + dp[i - 3]임을 알 수 있다.

 

위를 바탕으로 점화식을 세워보면

dp[i] = dp[i] + dp[i - 소수] 임을 알 수 있고,

미리 소수 판정을 했다면 위의 결과는 더 빠르게 진행될 수 있을 것이다.

 

#include <iostream>
#include <vector>
using namespace std;
int dp[100001];
bool p[100001];
vector<int>v;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    v.push_back(2);
    for(int i=3; i<=100000; i+=2){
        if(!p[i]){
            v.push_back(i);
            for(int j=2; j<=100000/i; j++) p[i*j]=1;
        }
    }
    dp[0]=1;
    for(int i=0; i<v.size(); i++){
        for(int j=1; j<=100000; j++){
            if(j<v[i]) continue;
            dp[j]=(dp[j]+dp[j-v[i]])%1000000007;
        }
    }
    int n, x; cin >> n;
    while(n--){
        cin >> x;
        cout << dp[x] << "\n";
    }
}