[BOJ][DP] 2225. 합분해

문제 -> https://www.acmicpc.net/problem/2225

자릿수가 증가함에 따라 어떻게 경우의 수를 구해야 할지

단순하게 생각해야 한다.

뭐든지, 문제는 단순화 시킨 후 확장.

예를들어 N = 7, K = 3인 상황을 생각해보자.

단순하게 

K자리에 N 부터 0 까지 차례대로 들어가고,

N - K자리에 있는 값을 합으로 가지는 K-1 자리의 dp값을 가져오면 된다.

즉, 점화식은 아래와 같다.

dp[i][j] += dp[i - 1][j - k];

(3중 for문으로 쓰여서 i, j, k가 쓰였다.) 

그림을 보면 이해가 될지도 모른다.

아래는 위 과정을 표로 나타냈다. 

소스(Github)