[백준] 3908번. 서로 다른 소수의 합(JAVA)

문제

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

---

풀이(25분)

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

public class Main {

    static final int MAX = 1120;
    static final int MAX_K = 14;
    static boolean[] isPrime = new boolean[MAX + 1];
    static List<Integer> primes = new ArrayList<>();
    static int[][] dp = new int[MAX + 1][MAX_K + 1];

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

        sieve();
        dp[0][0] = 1; // 초기값 설정: 0을 0개의 소수로 만드는 방법은 1가지

        // DP 계산
        for (int p : primes) {
            for (int i = MAX; i >= p; i--) {
                for (int k = 1; k <= MAX_K; k++) {
                    dp[i][k] += dp[i - p][k - 1];
                }
            }
        }

        // 쿼리 처리
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            System.out.println(dp[n][k]);
        }
    }

    // 에라토스테네스의 체
    static void sieve() {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= MAX; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= MAX; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        for (int i = 2; i <= MAX; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
    }
}

---

문제 풀이 전략

 

에라토스테네스의 체를 이용하여 모든 소수를 구해둔 뒤 dp를 적용한다.

dp는 단순하게 소수 하나를 고른 뒤 그 소수를 만들 수 있는 경우의 수를 더해주는 것이다.

 

예를 들면 dp[10][3]은 10을 3개의 소수로 만드는 방법을 의미한다.

그렇다면,

dp[10][3] += dp[10-2][2]

dp[10][3] += dp[10-3][2]

dp[10][3] += dp[10-5][2]

dp[10][3] += dp[10-7][2]

가 되는 것이다.

여기서 추가로 생각해보아야 할 부분은  2+5나 5+2나 동일하다는 것이다.

 

그렇기에

for (int i = MAX; i >= p; i--)

반복 조건을 쓴다.

예를 들어 다시 생각해보자.

for(int i = 1120; i >= 7; i--) 정도로 가정하자.

dp[1120][1] += dp[1113][0] 이 된다.

쭉 내려가면, dp[1120][1] += dp[7][0]이 된다. 

 

이런 방식으로 한번만 체크되게 문제를 해결하는 것이다.