[JavaScript] 백준 2225 합분해 (JS)

합분해

📚 문제 설명

---

0부터 N까지의 정수가 있다.
여기서 K개의 정수를 더해서 N을 만드는 경우의 수를 구하여라.

단, 1+2 와 2+1 은 서로 다른 경우의 수로 생각한다.

👨🏻‍💻 풀이 과정

---

dp[i][j] 은 i개의 숫자로 j를 만들 수 있는 경우의 수이다.
이 떄, N가 9이고 K가 3이면 dp[i][j]는 아래와 같다.

	0	1	2	3	4	5	6	7	8	9
K = 1	1	1	1	1	1	1	1	1	1	1
K = 2	1	2	3	4	5	6	7	8	9	10
K = 3	1	3	6	10	15	21	28	36	45	55

위의 예시를 보면 전체적인 규칙이 보인다.
dp[i][j]는 dp[i-1]의 0 ~ j 까지의 합과 같다.

따라서 dp[i][j] = dp[i][j - 1] + dp[i - 1][j] 이다.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let [N, K] = input[0].split(' ').map(Number);

    let dp = new Array(K);
	// 2차원 배열 생성 및 초기화.
    for (let i = 0; i < dp.length; i++) {
        dp[i] = new Array(N + 1).fill(1);
    }
	// dp 값 갱신. 
    for (let i = 1; i < dp.length; i++) {
        for (let j = 1; j < dp[0].length; j++) {
            for (let k = 1; k <= j; k++) {
                dp[i][j] = (dp[i - 1][k] + dp[i][k - 1]) % 1000000000;
            }
        }
    }
    console.log(dp[K - 1][N]);

🧐 후기

---

출력으로 1,000,000,000을 나눈 나머지를 출력해야 하는데 그 글을 못 봐서 조금 헤맸다. 그 외에는 규칙을 찾기 위해 손으로 직접 찾아보니 생각보다 쉽게 규칙을 찾을 수 있었던 문제였다.