hint

1부터 10000까지의 소수의 개수 : 1229개

들어가거나 안들어가거나를 1229개를 전부 하려 한다면, 2^1229개만큼의 프로그램이 돌아가게 되어 어디에서든 시간초과가 날 수밖에 없습니다.

그럼 이런 문제는 어떻게 접근해야할까요?

정답은, 다이나믹 프로그래밍 ( 동적 계획법 ) 입니다.

입출력 예제인 20을 보면,

3 17
7 13
2 5 13
2 7 11

으로 4가지가 나오게 되는데, 다음과 같이 보면 어떨까요?

D[i] = i보다 작거나 같은 소수들의 합으로 i를 만드는 방법의 수

위의 문제를 해결하는 방법이 조금 떠오르시나요? 쉽게 안떠오르는 분들은 아래의 식을 보시면서 이해하시면 좋습니다.

• dp[20] = 17 + dp[3] (1) => dp[3] = 3 로 1가지
• dp[20] = 13 + dp[7] (2) => dp[7] = 2,5 + 7 로 2가지
• dp[20] = 11 + dp[9] (1) => dp[9] = 2,7 로 1가지

점화식 : dp[j] = dp[j] + dp[ j - prime[i] ]

**핵심 소스

for(i=0 ; i < total_prime ; i++)
{
    for(j=n ; j>=0 ; j--)
    {
        dp[j] = dp[j] + dp[ j - prime[i] ] ;
    }
}

// n까지의 소수의 개수 : total_prime
// prime[i] = i번째 소수

시간복잡도 : O(N^2)
   

출처:pl0892029