[JAVA/자바] 백준 2225번: 합분해

문제 접근방법 N까지의 정수에 대해 K개로 표현할 수 있는 경우의 수를 dp[N][K]라고 할 때 dp[N][K] = dp[N-1][K-1] + dp[N-2][K-1] ... dp[0][2] 라는 식을 얻을 수 있다! 만약 N이 5고 K가 2라면?

0 5, 1 4, 2 3, 3 2, 4 1, 5 0 총 6개가 나온다. 이때 어떤 N이라고 K가 2라면 N+1개의 값을 갖는다는 것을 알아냈다.

만약 N이 5고 K가 3이라면? 위에서 구했던 2의 경우에서 0 5-> 2개 더해서 5가 되는 경우 dp[5][2] 1 4 -> 2개 더해서 4가 되는 경우 dp[4][2] 2 3 3 2 4 1 5 0 -> ...

를 구하면 되는 것을 알아냈다! 결국 dp[5][3] = dp[5][2] + dp[4][2] + ... dp[0][2] 라는 식을 구할 수 있다.

구한 점화식으로 풀이를..........