> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/dynamic-programming/sum-decomposition.md).

# Sum Decomposition

문제 복기

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.\
\
입력 : 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

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

> Ex1)\
> I : 20 2\
> O : 21

알고리즘 생각

1,2,3 더하기 문제 응용 & 확장판

변수가 N,K가 있기 때문에 1차원보다는 2차원 DP라고 생각해야한다!

1. **D\[k]\[n] : k개 정수로 합이 n을 만드는 경우의 수**
2. **D\[k]\[n] = ΣD\[k-1]\[n-L] (0<=n<=N, 0<=L<=n)**\
   L은 마지막에 오는 수를 의미한다. \
   이때 (new)K = K-1, (new)N = N-L 이 되고 나면 **L**은 **N-L 이하의 수**를 갖는다.\
   (new)N = N-L에서 L은 문제에서 주어지는 조건으로 인해 0<=L<=N 이므로, N = N \~0 즉, 0<=newN<=N 이 된다.\
   이때 **N-L**은 **변수 N과 같기 때문에 L의 범위는 0이상 n이하**라고 한다.

* 코드 구현 시 유의할 점\
  위의 점화식을 계산할 때 필요한 d\[0]\[0] = 1로 먼저 셋팅해준다!<br>