[boj] 2225. 합분해 (node.js)

문제 요약

[boj] 2225. 합분해 (node.js)

풀이

• DP로 풀이 가능한 경우의 수를 구하는 문제
• 모든 경우의 수를 시간 내에 구하기 위해 점화식을 세우고 풀이한다.
  • dp[N][k]: N개의 숫자로 K를 만들 수 있는 경우의 수
  • dp[N][k] = dp[N-1][0] + dp[N-1][1] + ... + dp[N-1][k]
    ( = dp[N-1][k] + dp[N][k-1] 로 구해도 동일하다.)

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

function solution() {
  const [N, K] = input().split(" ").map(Number);
  let dp = new Array(K + 1);
  dp[0] = new Array(N + 1).fill(0);
  dp[0][0] = 1;
  dynamic();
  console.log(dp[K][N]);

  function dynamic() {
    for (let i = 1; i <= K; i++) {
      dp[i] = [];
      for (let j = 0; j <= N; j++) {
        dp[i][j] = 0;
        for (let num = 0; num <= j; num++) {
          dp[i][j] += dp[i - 1][j - num];
        }
        dp[i][j] %= 1000000000;
      }
    }
  }
}

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});