[어려움][다이나믹 프로그래밍] 합분해

문제 링크 : https://www.acmicpc.net/problem/2225

합분해 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 7106 3061 2284 42.684% 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 1  20 2 예제 출력 1  21

[ 문제 풀이 ] 

D[K][N] = K개를 더해서 합이 N이 되는 수

[ 최종 구현(C++) ] 

#include <stdio.h>

int main(void)
{
	int N = 0, K = 0;
	long long D[201][201] = { 0LL };
	scanf("%d %d", &N, &K);

	D[0][0] = 1LL;

	for (int i = 1; i <= K; i++) // K
	{
		for (int j = 0; j <= N; j++) // N
		{
			for (int l = 0; l <= j; l++) // L
			{
				D[i][j] += D[i - 1][j - l];
				D[i][j] %= 1000000000;
			}
		}
	}

	printf("%lld\n", D[K][N]);

	return 0;
}