[백준, node.js] 2225번 "합분해" 문제 해결방법

[백준, node.js] 2225번 "합분해" 문제 해결방법

문제

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

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

예제 입력 & 출력

입력

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

출력

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

소스코드

문제 자체는 굉장히 단순해서 쉬울줄 알았으나 역시나 DP 문제는 점화식 구해내기가 정말 어러운 것 같다.

// 점화식
DP[K][N] = DP[K-1][0] + DP[K-1][1] + ... + DP[K-1][N]

const fs = require('fs');
let [n, k] = fs.readFileSync('./dev/stdin').toString().split(' ');
const dp = [];
k = Number(k)
n = Number(n);

// dp 세팅
// N = 0일 때, DP[N][K] = 1
// K = 1일 때, DP[N][K] = 1
for (let i = 1; i <= k; i++) {
  dp[i] = new Array(n + 1).fill(i === 1 ? 1 : 0);

  dp[i][0] = 1;
}

// *점화식* DP[K][N] = DP[K-1][0] + DP[K-1][1] + ... + DP[K-1][N]
for (let i = 2; i <= k; i++) {
  for (let j = 1; j <= n; j++) {
    dp[i][j] = dp[i-1].slice(0, j+1).reduce((acc, cur) => acc + cur, 0) % 1000000000;
  }
}

console.log(dp[k][n]);