Dynamic Programming 백준 알고리즘 자바 2225 ‘합분해’ 문제풀이

Problem

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

Input
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

Output
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

Solution

k=1 자리일 때, 합이 1이 되는 수는 1가지 경우, 2는 1가지, …. n은 1가지이다. k=2 자리일 때, 합이 1이 되는 수는 (0,1 / 1,0) 2가지 이다. 합이 2가 되는 수는 (0,2 / 1,1 / 2,0) 3가지이다. 이것은 첫번째 자리 수가 0이고 두번째 자리 수가 k=1일 때 합이 2가되는 경우와 첫번째 자리 수가 1이고 k=1일때 합이 1이 되는 수와 첫번째 자리 수가 2이고 k=1일때 합이 0이 되는 경우의 합과 같다. 따라서 합이 2가 되는 수는 dp[1][2] + dp[1][1] + dp[1][0]이다. dp[1][1] + dp[1][0] 은 dp[2][1]과 같다.

Code

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt(), k = scan.nextInt();
		
		int[][] dp = new int[k+1][n+1];
		for(int i = 0; i < n+1; i++)
			dp[1][i] = 1;
		
		for(int i = 2; i < k+1; i++) { // k
			dp[i][0] = 1;
			for(int j = 1; j < n+1; j++)
				dp[i][j] = (dp[i-1][j] + dp[i][j-1])%1000000000; 
		}
		System.out.println(dp[k][n]);
	}
}