백준 27519, 소수의 합

개요

문제 링크
골드 2, 정수론, DP
N을 서로 다른 소수의 합으로 표현하기

---

접근

1. DP에서는 knapsack에 가까우나 DP와 관련된 내용은 크지 않은 문제. 우선 100,000까지 체를 만들어야 하는 것은 쉽게 알 수 있다. 그리고 T가 10000번이니까 N=100,000까지 미리 값을 구해놓고 그 값을 T번 동안 출력만 해야 함을 알 수 있다.
2. 그러면 미리 구해놓을 때는 어떻게 구하냐, 이렇게 생각하자.
   1. 중복되지 않은 경우를 생각하면 오름차순이고, 구성이 모두 달라야 한다.
   2. 그럼 우선 2의 합으로 만들어진 모든 경우를 만든다. 이때는 모든 짝수의 경우가 1일 것이다.
   3. 그리고 3, 5, 7이 포함된 경우를 고려한다.
3. 이렇게 소수 크기대로 점차 큰 수가 포함된 경우의 수를 모두 더해주면 (소수개수 × N) 번에 해결된다. 이때는 모든 합의 경우가 오름차순으로 정렬되면서 중복되지 않는다. 왜일까? 아래 상황을 가정하자.

// n의 경우를 구하는 방법 = n-prime의 경우 더하기
// 겹치지 않는가? 에 대한 점검
n = A+p1 = B+p2
(p1 < p2)

만약 A,B의 구성이 같다고 생각하자. 그럼 A+p1 < B+p2가 되면서 가정에 어긋난다. 그럼 A,B의 구성은 반드시 다르다. 만약 p1 = p2라면? 그런 일은 없다. 루프를 돌때 같은 일을 두 번 하지는 않기 때문이다.
편의상 소수에 대해 루프를 돌 때 체를 구하면서 같이 해주자.

---

Pseudo code

dp[0] = 1
for (prime)
    for (n = 2~N)
        dp[n] += dp[n-prime]
dp[0] = 0

---

Source code

#include <iostream>
using namespace std;

#define N 100010
using ld = long long;
const int R=1e9+7;

bool p[N];
int dp[N];
void test() {
    int n;
    cin >> n;
    cout << dp[n] << "\n";
}

int main() {
    dp[0] = 1;
    for (ld i=2; i<N; i++)
        if (!p[i]) {
            for (ld j=i*i; j<N; j+=i)
                p[j] = 1;
            for (ld j=i; j<N; j++) {
                dp[j] += dp[j-i];
                dp[j] %= R;
            }
        }
    dp[0] = 0;

    int t;
    cin>>t;
    while(t--) test();
}