문제

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

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

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

예제

예제 입력 1

1
2
20 2

예제 출력 1

1
2
21

예제 입력 2

1
2
6 4

예제 출력 2

1
84

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const [N, K] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const DP = Array.from({ length: N + 1 }, (_, i) => {
  if (i === 1) return Array.from({ length: K + 1 }, (_, i) => i + 1);
  return new Array(K + 1).fill(1);
});

for (let i = 2; i <= N; i++) {
  for (let j = 1; j <= K; j++) {
    DP[i][j] = (DP[i - 1][j] + DP[i][j - 1]) % 1000000000;
  }
}

console.log(DP[N][K - 1]);
  • ✏️ N = 1인 경우 K = 1,2,3 …200 경우의 수를 생각해보았다.
    • ❗️ 1개의 수로 1을 만들 수 있는 경우의 수는 1가지이다.
    • 2개의 수로 1을 만들 수 있는 경우의 수는 0+1, 1+0으로 2가지이다.
    • 3개의 수로 1을 만들 수 있는 경우의 수는 0+0+1, 0+1+0, 1+0+0으로 3가지이다…
  • N = 2인 경우 K = 1,2,3 …200 경우의 수를 생각해보았다.
    • ❗️ 1개의 수로 2를 만들 수 있는 경우의 수는 1가지이다.
    • 2개의 수로 2를 만들 수 있는 경우의 수는 1+1, 2+0, 0+2로 3가지이다.
    • 3개의 수로 2를 만들 수 있는 경우의 수는 1+1+0, 1+0+1, 0+1+1, 2+0+0, 0+2+0, 0+0+2로 6가지이다…

❗️의 조건을 가지고 DP[N][k] 2차원 배열에서, DP[N][1] = 1인 것을 알 수 있다.

✏️의 조건을 가지고 DP[1][k] = K 인 것을 알 수 있다.

Frame.png

위와 같은 점화식을 발견하였고 그에 알맞은 식을 만들었다.