💡문제접근
- 에라토스테네스의 체로 2 ~ 40000 사이의 소수를 판별한 후 DP 점화식을 세워 문제를 해결할 수 있었다.
💡코드(메모리 : 115336KB, 시간 : 416ms, PyPy3로 제출)
import sys
input = sys.stdin.readline
prime_number = [True] * 40001
for i in range(2, int(40001**0.5)+1):
if prime_number[i]:
for j in range(2*i, 40001, i):
prime_number[j] = False
N = int(input())
dp = [1] + [0] * N
sosu = []
for i in range(2, 40001):
if prime_number[i]:
sosu.append(i)
for i in sosu:
for j in range(i, N+1):
dp[j] = (dp[j] + dp[j-i]) % 123456789
print(dp[N] % 123456789)
💡소요시간 : 17m