[백준 16400] 소수 화폐 [Java]

문제

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

 

---

풀이

N 이하의 소수들을 사용하여 N을 표현할 수 있는 방법의 수를 계산하는 문제다.

우선 N이하의 소수들을 구해주자.

    private static boolean isPrime(int num) {
        final int sqrtN = (int) Math.sqrt(num) + 1;
        for (int i = 2; i < sqrtN; ++i) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

        List<Integer> primeList = new ArrayList<>();
        for (int i = 2; i <= N; ++i) {
            if (isPrime(i)) {
                primeList.add(i);
            }
        }

dp[i] : 소수들의 합으로 숫자 i를 만드는 경우의 수

dp[i]의 i는 소수의 합이기 때문에 dp[i]는 dp[i - prime]에 prime을 더하는 경우의 수를 누적하면 된다.

즉 i이하의 소수를 순회하며 dp[i] = (dp[i] + dp[i - prime]) % MOD를 계산하면 된다.

소수 2를 처리하기 위해 dp[2-2] 를 1로 초기화하자.

      	int[] dp = new int[N + 1];
        dp[0] = 1;
        for (int prime : primeList) {
            for (int i = prime; i <= N; ++i) {
                dp[i] = (dp[i] + dp[i - prime]) % MOD;
            }
        }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/16400.java