[자바] 백준 16400 - 소수 화폐 (java)

목차

문제 : boj16400

 

 

필요 알고리즘

• 에라토스테네스의 체, DP (동적 계획법), 냅색 (배낭 문제), 정수론
  
  • 에라토스테네스의 체로 소수를 전처리 후, 냅색 DP를 돌려서 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  순서대로 생각해보자.

 

1. N이하의 화폐를 모두 알아야 한다.

-> 에라토스테네스의 체 등으로 N 이하의 모든 소수를 미리 구해두자. sqrt(N) 까지만 확인해본 이유는 '에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유' 글에 쓰여 있다.

private List<Integer> getPn(int limit) {
    List<Integer> pn = new ArrayList<>();
    boolean[] isPn = new boolean[limit+1];
    int sqrtN = (int)Math.sqrt(limit);
    for (int i = 3; i <= sqrtN; i+=2) {
        if (isPn[i]) continue;
        int base = i+i;
        while (base <= limit) {
            isPn[base] = true;
            base+=i;
        }
    }
    pn.add(2);
    for (int i = 3; i <= limit; i+=2) {
        if (!isPn[i]) pn.add(i);
    }
    return pn;
}

 

 

2. 이제 화폐를 알았으니, 그걸가지고 N원을 만들 수 있는 가짓수를 알 수 있어야 한다.

-> DP로 알 수 있다. 냅색 (배낭 문제)으로 유명한 DP 형태라 혹시 이하 코드가 이해가 안된다면 냅색을 공부해보자.

int[] dp = new int[n+1];
dp[0] = 1;
for (int cur : pn) {
    for (int i = cur; i <= n; i++) {
        dp[i] += dp[i-cur];
        dp[i] %= MOD;
    }
}
System.out.println(dp[n]);

 

 

3. 123,456,789로 나눈 나머지 값을 출력해야 한다.

-> 경우의 수가 기하급수적으로 커지므로 dp 진행 시 실제 값을 가지고 있으려면 BigInteger와 같은 느린걸 써야 한다. 그런데 나머지 연산에는 다음의 공식이 성립된다.

  따라서 마지막에 한 번 123,456,789로 나눈 나머지를 출력하는게 아니라 연산의 과정 중에 매번 나눈 나머지만 남겨둬도 결과값은 동일하다.

dp[i] %= MOD;

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
    private static final int MOD = 123456789;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private List<Integer> getPn(int limit) {
        List<Integer> pn = new ArrayList<>();
        boolean[] isPn = new boolean[limit+1];
        int sqrtN = (int)Math.sqrt(limit);
        for (int i = 3; i <= sqrtN; i+=2) {
            if (isPn[i]) continue;
            int base = i+i;
            while (base <= limit) {
                isPn[base] = true;
                base+=i;
            }
        }
        pn.add(2);
        for (int i = 3; i <= limit; i+=2) {
            if (!isPn[i]) pn.add(i);
        }
        return pn;
    }

    public void solution() throws Exception {
        List<Integer> pn = getPn(40000);
        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int cur : pn) {
            for (int i = cur; i <= n; i++) {
                dp[i] += dp[i-cur];
                dp[i] %= MOD;
            }
        }
        System.out.println(dp[n]);
    }
}