백준 2225. 합분해

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

2225번: 합분해

 

 

N과 K가 주어지고, 0~N까지의 숫자중 K개를 택해 N을 만들수 있는 경우의 수를 구해야 한다.

 

이 문제는 처음에 k개의 숫자로 0을 만드는 경우를 생각하지 못해서 어려웠다.

 

d[i][j] : i개의 숫자로 j를 만드는 경우의 수 

 

d[1][0] = 1개의 숫자로 0을 만드는 경우 = {0} 

d[1][1] = 1개의 숫자로 1을 만드는 경우 = {1} 

d[1][2] = 1개의 숫자로 2를 만드는 경우 = {2} 

... 

 

d[2][0] = 2개의 숫자로 0을 만드는 경우 = {0+0} 

d[2][1] = 2개의 숫자로 1을 만드는 경우 = {0+1, 1+1}

d[2][2] = 2개의 숫자로 2를 만드는 경우 = {0+2, 1+1, 2+0} 

...

 

k개의 숫자로 n을 만든다는 것은, k-1개의 숫자로 n을 만드는 경우에서 뒤에 숫자 하나를 더하는 경우 + k-1 개의 숫자로 n을 만드는 경우에서 뒤에 숫자 하나를 더하는 경우 ... 

 

점화식: 

d[i][j] = d[i-1][j-0] + d[i-1][j-1] + ... + d[i-1][j-j]