[BOJ/Java] 2225: 합분해

문제

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

0부터 `N`까지의 정수 `K`개를 더해서 그 합이 `N`이 되는 경우의 수를 구해야 한다.

덧셈의 순서가 다를 경우(1+2와 2+1)는 다른 경우이고, 한 개의 수를 여러 번 쓸 수도 있다.

• 1 ≤ `N` ≤ 200
• 1 ≤ `K` ≤ 200

답을 1,000,000,000으로 나눈 나머지를 출력해야 한다.

 

풀이

브루트 포스로 풀기에는 N과 K가 너무 커서 DP로 접근하려고 했다.

점화식을 어떻게 짜야할지 감이 잡히지 않아 30분 정도 고민하고 풀이를 봤다.

일주일 뒤 꼭 다시 풀어볼 것.

 

점화식은 다음과 같이 짤 수 있다.

숫자 `i`를 0부터 `n`의 숫자중에 `k`개를 이전 상태에서 더해나가는 식으로 `dp[k][n]`을 만든다.  

`dp[0][0]`은 아무 것도 선택하지 않았을 때의 경우의 수가 되므로 1로 초기화한다.

`dp[i][j]`는 `i`개의 수를 사용했을 때의 `j`가 되는 경우의 수가 된다.

 

오버플로우를 방지하기 위해 매 DP 계산마다 1,000,000,000으로 나눈 나머지를 넣는다.

 

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, k;
    static final int MOD = 1_000_000_000;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        // dp[k][n]은 k개의 숫자를 사용했을 때, n이 되는 경우의 수  
        long[][] dp = new long[k + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
        	long sum = 0;
            for (int j = 0; j <= n; j++) {
                sum = (sum + dp[i - 1][j]) % MOD;
                dp[i][j] = sum;
            }
        }

        System.out.println(dp[k][n]);
    }
}