[백준][dp] 2225 합분해 NodeJs 구현

목차

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

문제

 

문제에 대한 생각 흐름

먼저 0~5 로 한번 생각을 해보았다.

0~5 1개 -> 1

0~5 2개 -> 6

0~5 3개 -> 21 (올바른 답인데 코드 돌려서 앎 직접 노가다로 못구함)

이렇게 보니 이전 것들의 누적일 것이라는 생각이 들었고 직접 표를 작성해 보았다.

 

 

 

점화식 규칙을 찾기 위한 표

가로: N 세로: K

1	1	1	1
1	2	3	4
1	3	6	10
1	4	10	20
1	5	15	35

 

이렇게 보니 무언가 보인다! 

바로 dp[i][j] = dp[i][j-1] + dp[i-1][j] 라는 점화식이 구해진다.

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let [a, b] = input[0].split(" ");
a = Number(a);
b = Number(b);

let dp = Array.from(Array(202), () => Array(202));
for (let i = 0; i <= 200; i++) {
  dp[0][i] = 0;
  dp[1][i] = 1;
  dp[i + 1][0] = 1;
}
for (let i = 2; i <= 200; i++) {
  for (let j = 1; j <= 200; j++) {
    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000;
  }
}

console.log(dp[b][a]);