[백준 JAVA]2225 — 합분해

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

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

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

import java.util.Scanner;

public class Main {
	private final static int MOD = 1000000000;
	//k개를 더해서 n을 만드는경우의수
	private static long dp[][];

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		dp = new long[k+1][n+1];
		for (int i = 0; i <= n; i++) {
			dp[1][i] = 1;
		}
		
		System.out.println(Decomposition(k, n));
		
		
	}
	//숫자 i를 j개의 합으로 나타내는 경우의수
	private static long Decomposition(int k , int n) {
		for (int i = 1; i <= k; i++) {
			for(int j = 0 ; j <= n ; j ++) {
				for (int l = 0; l <= j; l++) {
					dp[i][j] += dp[i-1][j-l];
					dp[i][j] %= MOD;
				}
				
			}
		}
		return dp[k][n];
	}

}

그동안 dp문제라고 해당함수의 재귀적인것만 생각하다가 피봤다..
for문을통해서 기존데이터로 bottom-up방법으로 문제를 푸는데 사용한 점화식은 DP[K][N] = DP[k-1][N-L] (0 ≤ L ≤ N) 또한,
어떤수든 k=1 일시 경우의수는 1가지이므로 dp[1][i] = 1;로 초기화. 이 값을 통해 DP[K][N]을 만들어간다. 이 개념이 직관적으로는 상상이안가지만
실제로 점화식을 풀어서 예로들어
DP[2][2] = DP[1][2] + DP[1][1] + DP[1][0]; 여기서 DP[1][i] 값들은 모두 1로 초기화되었으니 바로 DP[2][2] = 3이나온다.. wow.. 아름답다
중요한점!!! dp의 값이 n(n-1)(n-2)…1 개 즉 n!에다가 k 또한마찬가지로
k!*n! 만큼의 값이 나올수있다. 따라서 int 로는 안되고 long값을 써야한다..
그런데 여기서 문제에서 값을 10억으로나눈 나머지를 요구하는데 이값을
점화식에서구한다음에 바로 추가한다.

dp[i][j] += dp[i-1][j-l];
dp[i][j] %= MOD;

이부분을 무시하고 마지막 출력값에 %MOD를 하면 값이다르다 .. 왜지..?
계산시마다 %MOD를 해줘야한다..

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