2225 - 합분해
합분해
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
D[k][n]: 0~N 수를 K번 이용해 합이 N이 되는 경우 수
정의를 먼저하고 점화식을 생각해보자
- 규칙이 있는가? k=2, n=3 인경우 다음과 같다
0+3, 1+2, 2+1, 3+0
K번 중에 마지막 수 (K-1) 를 선택했을 경우를 생각해보면?
D[2][3] = D[1][3] + D[1][2] + D[1][1] + D[1][0]
D[1][3]: 선택한 수가 0 이었을 때 합이 3이 되는 경우
D[1][2]: 선택한 수가 1 이었을 때 합이 2이 되는 경우
D[1][1]: 선택한 수가 2 이었을 때 합이 1이 되는 경우
D[1][0]: 선택한 수가 3 이었을 때 합이 0이 되는 경우
D[k][n]는 D[k-1][0] + D[k-1][1] + ... + D[k-1][n]