[JAVA/백준/16400] 소수 화폐 / DP

 

16400번: 소수 화폐

 

풀이 과정

• 처음엔 모든 경우의 수를 따져가며 규칙을 찾았다
  • 2 = 2
  • 3 = 3
  • 4 = 2 + 2
  • 5 = 2 + 3, 5
  • 6 = 2 + 2 + 2, 3 + 3
  • 7 = 2 + 2 + 3, 2 + 5, 7
  • 8 = 2 + 2 + 2 + 2, 2 + 3 + 3, 3 + 5
• 현재 수에서 소수만큼을 뺀 경우의 수를 모두 더하면 될 것 처럼 생겼다
• 우선 에라토스테네스의 체를 만들어 소수를 뽑았다
• 그 후 dp 배열을 만들고 dp[0] = 1을 넣은 다음에 점화식을 다음과 같이 유도했다
  • case 2
    • dp[2] += dp[2 - 2]
    • dp[3] += dp[3 - 2]
    • dp[4] += dp[4 - 2]
    • dp[5] += dp[5 - 2]
    • dp[6] += dp[6 - 2]
    • ...
  • case 3
    • dp[3] += dp[3 - 3]
    • dp[4] += dp[4 - 3]
    • dp[5] += dp[5 - 3]
    • dp[6] += dp[6 - 3]
    • dp[7] += dp[7 - 3]
    • ...
  • case 5
    • dp[5] += dp[5 - 5]
    • dp[6] += dp[6 - 5]
    • dp[7] += dp[7 - 5]
    • dp[8] += dp[8 - 5]
    • dp[9] += dp[9 - 5]
    • ...

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

  public static void main(String[] args) throws IOException {
    Main.start();
  }


  private static void start() throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	// 에라토스테네스의 체를 위한 isPrime 배열
    boolean[] isPrime = new boolean[40001];
    Arrays.fill(isPrime, true);

    isPrime[1] = false;
    for (int i = 2; i < isPrime.length; i++) {
      if (isPrime[i] == true) {
        for (int j = i * 2; j < isPrime.length; j += i) {
          isPrime[j] = false;
        }
      }
    }

    int N = Integer.parseInt(br.readLine());
 	// DP를 위한 dp배열
 	int[] dp = new int[N + 1];

    dp[0] = 1;

    for (int i = 2; i <= N; i++) {
      // 소수일 경우만 점화식을 계산
      if (isPrime[i] == true) {
        for (int j = i; j <= N; j++) {
          dp[j] += dp[j - i] % 123456789;
          dp[j] %= 123456789;
        }
      }
    }

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

  }
}