2225 합분해 (자바스크립트)

문제

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

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

입력

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

출력

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

====

문제 분석

0부터 N까지의 수를 여러 번 사용해서라도 조합을 만든 뒤 해당 숫자들의 합이 N이 되는 경우의 수를 출력하는 문제이다.

이러한 문제는 보통 1부터 N까지의 숫자를 인덱스를 가지는 dp를 만든 뒤 dp[i][j] 를 이전 i j 들의 조합들로 점화식을 만들면 됐다. 

이 문제도 처음에는 위 방식으로 dp를 만든 뒤 점화식을 도출할려고 했는데, 이 문제에서는 k개만을 사용하여 조합을 만들어야 했으며 숫자가 0부터 사용할 수 있다는 특이점이 있었다. 만약 5라는 숫자를 5개의 숫자 조합으로 만든다면 0,0,0,0,5 로 만들 수 있다. 또 5,0,0,0,0 으로 만들 수도 있다. 이러한 특이점을 해결하기 위해 나는dp를 2차원 배열로 만들어서 행은 k개를 기준으로 열은 n을 기준으로 만들었다.

const dp = Array.from({ length: k + 1 }, () =>
    Array.from({ length: n + 1 }).fill(0)
);

0부터 n까지 숫자를 숫자 1개를 이용해서 만드는 방법은 각각 1이므로 dp[1][0~n] = 1 이다.

for (let i = 0; i < n + 1; i++) {
    dp[1][i] = 1;
}

이때 숫자 0을 k개를 만드는 방법은 항상 0 , 00, 000, 0000 과 같은 항상 1가지이다.

for (let i = 0; i < k + 1; i++) {
    dp[i][0] = 1;
}

숫자 1을 2개 조합을 만드는 방법은 

1) 숫자 1을 1개 만드는 조합에서 0을 추가하기 -> dp[0][1]

2) 숫자 0을 1개로 만드는 조합에서 1을 추가하기 -> dp[0][0]

더 나아가 숫자 3을 3개 조합으로 만드는 방법은

1) 숫자 3을 2개로 만드는 조합에서 0을 추가하기 -> dp[2][3]

2) 숫자 2를 2개로 만드는 조합에서 1을 추가하기 -> dp[2][2]

2) 숫자 1을 2개로 만드는 조합에서 2를 추가하기 -> dp[2][1]

2) 숫자 0을 2개로 만드는 조합에서 3을 추가하기 -> dp[2][0]

이를 통해 점화식이 dp[i][j] = dp[i][j]+ dp[i-1][j~0] 를 알 수 있다.

for (let i = 2; i < k + 1; i++) {
    for (let j = 1; j < n + 1; j++) {
        for (let k = j; k >= 0; k--) {
            dp[i][j] = (dp[i][j] + dp[i - 1][k]) % INF;
        }
    }
}

 문제 출력에서 1_000_000_000으로 나눈 나머지를 출력하라해서 INF를 추가한 것임

정답 코드

const main = (n, k) => {
    const INF = 1_000_000_000;
    const dp = Array.from({ length: k + 1 }, () =>
        Array.from({ length: n + 1 }).fill(0)
    );
    for (let i = 0; i < n + 1; i++) {
        dp[1][i] = 1;
    }
    for (let i = 0; i < k + 1; i++) {
        dp[i][0] = 1;
    }
    for (let i = 2; i < k + 1; i++) {
        for (let j = 1; j < n + 1; j++) {
            for (let k = j; k >= 0; k--) {
                dp[i][j] = (dp[i][j] + dp[i - 1][k]) % INF;
            }
        }
    }
    console.log(dp[k][n]);
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, k] = input[0].split(' ').map((v) => +v);
main(n, k);