백준 2225번: 합분해 - javascript

백준 2225번: 합분해

문제 설명

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

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

입력

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

출력

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

접근

여태까지는 1차원적인 dp문제만 풀다보니 처음에는 자연스레 1차원적인 접근을 하면서 시간을 허비했다.
하지만 이번 문제는 N 과 K, 2개의 입력변수가 주어진다. 그 뜻은 2차원 행렬의 dp문제라는 뜻이다.

K\N	0	1	2	3	4	5…
0	0	0	0	0	0	0
1	1	1	1	1	1	1
2	1	.	.	.	.	.
3	1	.	.	.	.	.

이런식의 표가 등장하게 된다. 모든 N에 대하여 1개의 수의 합으로 표현하려면 N자기자신 1번 밖에 없다.
여기서 N=5, K=2인 경우를 구하려면 어떻게 해야할까? 표 없이 생각해보자.

5 = 5 + (N=0, K=1)
  + 4 + (N=1, K=1) 
  + 3 + (N=2, K=1)
  + 2 + (N=3, K=1)
  + 1 + (N=4, K=1)
  + 0 + (N=5, K=1)

문제 설명에서 [덧셈의 순서가 바뀐 경우는 다른 경우로 센다] 라고 했으니, 5더하기 N=0일 경우와 0더하기 N=5일 경우는 다르다.
그러면 위의 표로 다시 돌아가면 우리는 K가 1일때 N이 0부터5까지의 모든 경우를 다 알고있다. dp(N=5, K=2) = 1+1+1+1+1+1 = 6 이 된다.

이렇게 하면 우리는 고정된 N에 대해서 K의 변동이 있는 풀이를 알게 됬다.

K\N	0	1	2	3	4	5…
0	0	0	0	0	0	0
1	1	1	1	1	1	1
2	1	2	3	4	5	6
3	1	.	.	.	.	.

그런데 2번째 줄까지 입력하다보면 dp[i][j]는 dp[i-1][j] + dp[i][j-1]의 합과 같다는 것을 알 수 있다.

그냥 dp[i][j] = sum(dp[i-1][0] + dp[i-1][1] + dp[i-1][2]+ … + dp[i-1][j]) 해도 되지만 더 좋은 식이 있기도하고, 2차원 행렬의 dp문제니깐 n 과 k 모두 이전 결과를 가지고 다음 결과값을 찾아내는게 더 좋아보여서 그렇게 짰다…

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  input = input[0].split(' ');
  let n = parseInt(input[0]);
  let k = parseInt(input[1]);
  let answer = matrix_dp(n,k);
  console.log(answer);
  process.exit();
});

function matrix_dp(n,k){
  let arr = [];
  for(let i=0;i<=k;i++){
    arr[i] = new Array(n+1);
  }  
  for(let i=0;i<=n;i++){
    arr[1][i] = 1;
  }
  for(let i=2;i<=k;i++){
    for(let j=0;j<=n;j++){
      if(j==0) {
        arr[i][j] =1;        
      }else{        
        arr[i][j] = (arr[i][j-1] + arr[i-1][j])%1000000000;
      }      
    }
  }
  return arr[k][n];
}