[Algorithm] 합분해 (백준 - 2225)

문제

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

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

입력

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

출력

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

입출력 예

예제 입력	예제 출력
20 2	21

풀이

전형적인 DP 문제이다. 최종적으로 합이 n이 되는 모든 경우의 수를 계산하기 위해서는 이전에 만들었던 값을 이용하면서 계산할 수 있다. 점화식은 다음과 같다.

 

DP[i][j] = j개를 사용해서 i를 만드는 경우의 수

 

만약 10(n)를 3(k)개의 수를 더해서 만들어야 할 때 다음과 같이 계산한다.

• 0개 숫자를 사용하는 경우 만들 수 있는 수가 없으므로 모두 0 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0 ]
• 1개 숫자를 사용하는 경우 만들어야 하는 숫자가 곧 이용할 숫자로 모두 1 [ 1, 2, 3, 4,  5, 6, 7, 8, 9, 10, 11 ]

여기까지가 초기화 단계이다. 이제 2개 숫자를 사용해서 각 숫자(1~10)을 만드는데 이는 이전의 DP를 이용하기 시작한다. 예를 들어 10을 숫자 두개를 이용해서 만드는 경우에는 다음과 같은 경우들이 있다.

 

• DP[1][1] (숫자 1개를 이용해서 1을 만드는 경우) + 9
• DP[1][2] (숫자 1개를 이용해서 2을 만드는 경우) + 8
• DP[1][3] (숫자 1개를 이용해서 3을 만드는 경우) + 7
• DP[1][4] (숫자 1개를 이용해서 4을 만드는 경우) + 6
• DP[1][5] (숫자 1개를 이용해서 5을 만드는 경우) + 5
• DP[1][6] (숫자 1개를 이용해서 6을 만드는 경우) + 4
• DP[1][7] (숫자 1개를 이용해서 7을 만드는 경우) + 3
• DP[1][8] (숫자 1개를 이용해서 8을 만드는 경우) + 2
• DP[1][9] (숫자 1개를 이용해서 9을 만드는 경우) + 1
• DP[1][10] (숫자 1개를 이용해서 10을 만드는 경우) + 0

이 다음으로 숫자 2개를 이용해서 각 숫자를 만드는 경우는 위와 동일하게 다음과 같다.

• DP[2][1] (숫자 2개를 이용해서 1을 만드는 경우) + 9
• DP[2][2] (숫자 2개를 이용해서 2을 만드는 경우) + 8
• DP[2][3] (숫자 2개를 이용해서 3을 만드는 경우) + 7
• DP[2][4] (숫자 2개를 이용해서 4을 만드는 경우) + 6
• DP[2][5] (숫자 2개를 이용해서 5을 만드는 경우) + 5
• DP[2][6] (숫자 2개를 이용해서 6을 만드는 경우) + 4
• DP[2][7] (숫자 2개를 이용해서 7을 만드는 경우) + 3
• DP[2][8] (숫자 2개를 이용해서 8을 만드는 경우) + 2
• DP[2][9] (숫자 2개를 이용해서 9을 만드는 경우) + 1
• DP[2][10] (숫자 2개를 이용해서 10을 만드는 경우) + 0

이를 사용할 숫자의 수인 k번 반복하고 각각 반복문이 한 번 더 수행되는데  n번 반복하게 된다. 모든 과정을 거치게 되면 DP[k][n]이 답이 된다. 추가적으로 이전 값을 이용해서 현재 값을 구할 때 문제 조건 중 주의해야 할 사항이 있는데 계산할때마다  1,000,000,000으로 나눈 나머지를 저장해야 한다. 마지막에 한 번만 해주게 되면 계산 과정 중 값이 허용가능 한 숫자를 넘겨 계산이 불가능해지는 경우도 존재한다. 또는 BigInt를 사용해서 계산하고 마지막에 한 번만 계산할 수 있다.

 

코드

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : "./testcase/2225.txt";

const inputs = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, k] = inputs[0].split(" ").map(Number);

const dp = [...Array(k + 1)].map((_) => new Array(n + 1).fill(0));
for (let i = 0; i <= n; i++) dp[1][i] = 1;

for (let i = 2; i <= k; i++) {
  for (let j = 0; j <= n; j++) {
    for (let jj = 0; jj <= n; jj++) {
      if (j + jj > n) continue;
      dp[i][j + jj] = (dp[i][j + jj] + dp[i - 1][j]) % 1000000000;
    }
  }
}
console.log(dp[k][n]);