[백준] 16400번 소수 화폐

💡문제접근

• 에라토스테네스의 체로 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