백준 16400번

문제

https://www.acmicpc.net/problem/16400

알고리즘

1. 소수 구하기(에라토스테네스의 체)

2. 구해진 소수로 다이나믹 프로그래밍에 사용

풀이

1. 화폐를 소수만 이용하니 구입하려는 가격 범위 내에 소수를 모두 가져온다.
2. 이제 구해진 소수로 dp 배열을 정의해야한다.
   •     dp[i]는 숫자 i를 소수들의 합으로 만들 수 있는 경우의 수를 의미한다. 이 배열을 크기 N + 1로 정의하고, 초기값을 설정한다.
   •     dp[0] = 1 (0을 만들 수 있는 방법은 아무것도 선택하지 않는 1가지)
3. dp배열 업데이트
   •     소수들을 하나씩 돌면서 dp배열을 갱신, 소수를 사용해 숫자 i를 만들 수 있는 경우를 누적해서 계산한다.

   • 소수 2로 갱신
     dp[2] = dp[2] + dp[0] = 0 + 1 = 1 (2를 소수 2 하나로 만들 수 있음)
     dp[3] = dp[3] + dp[1] = 0 + 0 = 0
     dp[4] = dp[4] + dp[2] = 0 + 1 = 1 (4는 2 + 2로 만들 수 있음)
     dp[5] = dp[5] + dp[3] = 0 + 0 = 0
     dp[6] = dp[6] + dp[4] = 0 + 1 = 1 (6은 2 + 2 + 2로 만들 수 있음)
     dp[7] = dp[7] + dp[5] = 0 + 0 = 0
     dp[8] = dp[8] + dp[6] = 0 + 1 = 1 (8은 2 + 2 + 2 + 2로 만들 수 있음)
     dp[9] = dp[9] + dp[7] = 0 + 0 = 0
     dp[10] = dp[10] + dp[8] = 0 + 1 = 1 (10은 2 + 2 + 2 + 2 + 2로 만들 수 있음)

   • 소수 3으로 갱신
     dp[3] = dp[3] + dp[0] = 0 + 1 = 1 (3을 소수 3 하나로 만들 수 있음)
     dp[4] = dp[4] + dp[1] = 1 + 0 = 1
     dp[5] = dp[5] + dp[2] = 0 + 1 = 1 (5는 3 + 2로 만들 수 있음)
     dp[6] = dp[6] + dp[3] = 1 + 1 = 2 (6은 3 + 3, 또는 2 + 2 + 2로 만들 수 있음)
     dp[7] = dp[7] + dp[4] = 0 + 1 = 1 (7은 3 + 2 + 2로 만들 수 있음)
     dp[8] = dp[8] + dp[5] = 1 + 1 = 2 (8은 3 + 3 + 2 또는 2 + 2 + 2 + 2로 만들 수 있음)
     dp[9] = dp[9] + dp[6] = 0 + 2 = 2 (9는 3 + 3 + 3 또는 3 + 2 + 2 + 2로 만들 수 있음)
     dp[10] = dp[10] + dp[7] = 1 + 1 = 2 (10은 3 + 3 + 2 + 2 또는 2 + 2 + 2 + 2 + 2로 만들 수 있음)

4. 위 방식으로 계산을 하고 배열의 마지막 값을 프린트한다.

코드

import sys
input = sys.stdin.read

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    primes = [i for i in range(2, n + 1) if is_prime[i]]
    return primes

def solve():
    N = int(input())
    MOD = 123456789

    primes = sieve(N)

    dp = [0] * (N + 1)
    dp[0] = 1

    for prime in primes:
        for i in range(prime, N + 1):
            dp[i] = (dp[i] + dp[i - prime]) % MOD

    print(dp[N])