[2225] 합분해

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

 

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

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

 

---

<풀이>

 

 먼저 예시를 들어서 이해를 해보자면, 간단하게 n=2, k=2라고 해보았다.

그럼 0-2 사이의 정수 2개를 더하여 2가 되는 경우의 수를 구하면 된다.

• 0,2

• 1,1

• 2,0

-> 위와 같이 세 가지 경우의 수가 등장한다.

이것을 배열로 표현해보자면 dp[2][2]=3 인 것이다.

 

 

그럼 이제 위의 세 가지 경우의 수를 가지고 점화식을 세워보겠다.

먼저 0, 2의 경우를 보자. 앞의 정수가 0일 경우, 합이 2가 되려면 당연히 2가 와야 한다.

이 2라는 값은 숫자가 한 개이고, 동시에 합이 2다. 그러므로 이 2를 배열로 표현하자면,

이렇게 나타낼 수 있다.

 

한 가지만 예시로 들면 아직 이해하기 어려우므로, 이어서 1,1을 보겠다.

앞의 정수가 이번에는 1이다. 그럼 그 다음 합으로는 당연히 2-1 = 1이 와야 한다.

이 1이라는 값은 숫자가 한 개이고, 동시에 합이 1이다. 그러므로 1을 표현한다면 아래와 같이 표현할 수 있다.

 

 

그럼 이제 마지막으로 2,0의 경우에 0은 자연스럽게 dp[1][0] 이라고 표현할 수 있는 것을 알 수 있다.

 

이 것을 통해 점화식을 세운다면,

dp[i][j] += dp[i-1][j-l] 이라고 세울 수 있다. 좀 더 자세히 설명하자면,

 

 

이 것을 바탕으로 코드를 짜면 아래와 같이 나온다.

import java.util.*;
import java.math.*;

public class Q2225 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		long[][] d = new long[k + 1][n + 1];
		d[0][0] = 1;
		for (int i = 1; i <= k; i++) {
			for (int j = 0; j <= n; j++) {
				for (int l = 0; l <= j; l++) {
					d[i][j] += d[i - 1][j - l];
					d[i][j] %= 1000000000;
				}
			}
		}
		System.out.println(d[k][n]);
	}
}

※ 참고로 1000000000을 for문 안에서 나눈 이유는 오버플로우 현상을 방지하기 위해서임.