소수 화폐

---

풀이 방법

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

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

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

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static boolean[] infinite;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1];
        infinite = new boolean[N + 1];

        for (int i = 2; i <= N; i++) {
            if (!infinite[i]) {
                int x = 2 * i;
                while (x <= N) {
                    infinite[x] = true;
                    x += i;
                }
            }
        }

        dp[0] = 1;

        for (int i = 2; i <= N; i++) {
            if (!infinite[i]) {
                for (int j = i; j <= N; j++) {
                    dp[j] = (dp[j] + dp[j - i]) % 123456789;
                }
            }
        }

        System.out.println(dp[N]);
    }
}