[ BOJ ][JAVA][16400] 소수 화폐

www.acmicpc.net/problem/16400

16400번: 소수 화폐

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	494	230	185	49.333%

문제

소수나라는 특이하게 모든 소수(prime number)를 화폐 단위로 사용한다.

소수나라에 놀러 온 하나는 관광을 하다가 가격이 N인 물건을 발견하고 너무 마음에 들어 999983원을 내고 구매하려고 했다. 하지만 상점 주인이 거스름돈이 없어 정확히 N원을 지불해달라고 하였다.

물건을 구매하려던 하나는 소수나라의 화폐를 이용하여 N원을 정확히 만들 수 있는 방법의 가짓수가 얼마나 되는지 궁금해졌다.

하나를 도와 N원을 지불하기 위한 가짓수가 얼마나 되는지 구해보자.

단, 하나는 소수나라의 모든 화폐가 무한정 있다고 가정한다.

입력

구매하려고하는 물건의 값 N(2 ≤ N ≤ 40,000, N은 정수)이 주어진다.

출력

소수나라의 화폐를 이용하여 지불할 수 있는 방법의 수를 출력한다.

단, 지불할 수 있는 방법의 수가 매우 크기때문에, 123,456,789로 나눈 나머지 값을 출력한다.

예제 입력 1

8

예제 출력 1

3

코드

/*
    소수화폐
    소수구하기 + DP(동전 바꾸기)
*/
import java.io.*;
import java.util.*;
public class p16400 {
    static final int MOD = 123456789;
    static int n, cnt, size;
    static List<Integer> primeList;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        primeList = new ArrayList<>();
        boolean[] prime = new boolean[40001];
        // true : 소수가 아니다, false : 소수이다.
        prime[0] = true;
        prime[1] = true;
        for (int i = 2; i <= 40000; i++) {
            if (!prime[i]) {
                for (int j = i * i; j <= 40000; j += i) {
                    prime[j] = true;
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            // 소수인 것들 중에서
            if (!prime[i]) {
                primeList.add(i);
            }
        }
        // dp[n] : 가격 n을 소수화폐로 살수 있는 경우의 수
        dp = new int[40001];
        dp[0] = 1;
        for (int i = 0; i < primeList.size(); i++) {
            int tmp = primeList.get(i);
            for (int j = tmp; j <= n; j++) {
                dp[j] = (dp[j] + dp[j - tmp]) % MOD;
            }
        }
        System.out.println(dp[n]);
    }
}

/*  DP(동전바꾸기) 점화식 도출 과정
    tmp = 2
    dp[2] = dp[2] + dp[2-2]; // 0 + 1
    dp[3] = dp[3] + dp[3-2]; // 0 + 0
    dp[4] = dp[4] + dp[4-2]; // 0 + 1
    dp[5] = dp[5] + dp[5-2]; // 0 + 0
    dp[6] = dp[6] + dp[6-2]; // 0 + 1
    dp[7] = dp[7] + dp[7-2]; // 0 + 0
    dp[8] = dp[8] + dp[8-2]; // 0 + 1
    ...
    dp[n] = dp[n] + dp[n-2]; // ?
    tmp = 3
    dp[3] = dp[3] + dp[3-3]; // 0 + 1
    dp[4] = dp[4] + dp[4-3]; // 1 + 0
    dp[5] = dp[5] + dp[5-3]; // 0 + 1
    dp[6] = dp[6] + dp[6-3]; // 1 + 1
    dp[7] = dp[7] + dp[7-3]; // 0 + 1
    dp[8] = dp[8] + dp[8-3]; // 1 + 1
    ...
    dp[n] = dp[n] + dp[n-3];  // ?
    tmp = 5
    dp[5] = dp[5] + dp[5-5]; // 1 + 1
    dp[6] = dp[6] + dp[6-5]; // 2 + 0
    dp[7] = dp[7] + dp[7-5]; // 1 + 1
    dp[8] = dp[8] + dp[8-5]; // 2 + 1
    ...
*/