백준 2225 - 합분해

Java

2225 번 - 합분해

문제

접근 방법

0부터 n까지의 정수를 K개 사용하여 정수 N을 만든다고 가정하면 점화식은 다음과 같이 생각 할 수 있다.

정수 K - 1개로 정수 N을 만든 경우의 수가 a개 있다면, 여기서 0을 추가하여 K개의 정수로 N을 만드는 경우의 수가 a가 된다.
K - 1개로 정수 N - 1을 만든 경우의 수가 b개 있다면, 여기서 1을 추가하여 K개의 정수로 N을 만드는 경우의 수가 b가 된다.
K - 1개로 정수 N - 2을 만든 경우의 수가 c개 있다면, 여기서 2을 추가하여 K개의 정수로 N을 만드는 경우의 수가 c가 된다.
… K - 1개로 정수 0을 만든 경우의 수가 z개 있다면, 여기서 n을 추가하여 K개의 정수로 N을 만드는 경우의 수가 z가 된다.

위 경우를 다 합하면 K 개로 N을 만드는 경우의 수는 a + b + c + d + … + z 개가 된다.

즉, k-1개의 정수로 N을 만드는 경우의 수를 모두 합한것이, k 개의 정수로 N을 만드는 경우의 수이다.

따라서 점화식은 다음과 같다.

dp[k][n] = dp[k][n - 1] + dp[k - 1][n - 1]

코드

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

public class Main {
	static int n, result, k;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
    	int[][] dp = new int[k][n + 2];

    	Arrays.fill(dp[0], 1);
		// N을 만들기 위한 정수의 개수
    	for(int i = 1; i < k; i++) {
			// 정수 i개를 써서 j를 만드는 총 경우의 수
    		for(int j = 1; j < n + 2; j++) {
    			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000;
    		}
    	}

    	System.out.println(dp[k - 1][n + 1]);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}