백준 27519 - 소수의 합 (C++)

문제

• 문제 링크

  
   BOJ 27519 - 소수의 합 
  

• 문제 요약

함수 $f(n)$을 "$n$을 $0$개 이상의 소수의 합으로 표현하는 경우의 수" 라고 정의하자.
$T$개의 $n$이 주어질 때, 각 $n$에 맞는 $f(n)$의 값을 출력해보자.

• 제한

TL : $3$ sec, ML : $128$ MB




$1 ≤ T ≤ 10,000$

$0 ≤ n_i ≤ 100,000$

알고리즘 분류

• 수학(math)
• 정수론(number_theory)
• 소수 판정(primality_test)
• 에라토스테네스의 체(sieve)
• 다이나믹 프로그래밍(dp)

풀이

웰노운스러운 유형 중 하나이다.

$dp[n]$을 $f(n)$그대로 정의할 때, 소수들을 매개로 진행하는 $knapsack$ $problem$으로 바라볼 수 있다.

$dp[0] = 1$을 기저 사례로 잡고 $n_i$의 구간 내 존재하는 모든 소수들에 대해 냅색$dp$를 돌려주면 되겠다.

보통 물건의 개수가 $1$개임에 따라 현재 시행의 여파를 다음 시행부터 받도록 뒤에서부터 $dp$를 진행한다.
하지만 이번 문제에선 소수들을 중복해서 사용할 수 있으므로, 앞에서부터 진행해도 무방하다.

구간에 대해 $O(n√n)$ 수준의 소수 판정을 해도 범위 상 충분해 보이고, 맘편히 $sieve$를 돌려도 될 듯 하다.
나는 $sieve$를 진행하며 소수가 등장할 때마다 위 $dp$를 진행하였다.

전체 코드

#include<bits/stdc++.h>
#define N 100001
 
std::bitset <N> p;
int dp[N]{ 1 };
 
int main()
{
    for (int i(2); i < N; i++)
        if (!p[i])
        {
            for (int j(i + i); j < N; j += i)
                p[j] = 1;
 
            for (int j(i); j < N; j++)
            {
                dp[j] += dp[j - i];
                if (dp[j] > 1000000007)
                    dp[j] -= 1000000007;
            }
        }
    int t; scanf("%d", &t);
    while (t--)
    {
        int n; scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
}

comment

끝