BOJ 2225 합분해

문제

 

2225번: 합분해

 

예시 코드

function solution() {
  const MOD = 1000000000;
  const [N, K] = input().split(" ").map(Number);
  const dp = Array.from(Array(N + 1), () => Array(K + 1).fill(0));

  dp[0][0] = 1;
  for (let i = 1; i <= K; i++) {
    for (let j = 0; j <= N; j++) {
      dp[j][i] = dp[j][i - 1];
      if (j >= 1) dp[j][i] += dp[j - 1][i];
      dp[j][i] %= MOD;
    }
  }

  return dp[N][K];
}

 

풀이

이 문제는 DP를 이용해 풀 수 있는데요.

이해하는 데 필요한 두 가지 포인트를 알아보겠습니다.

1. dp[j][i] 값은 'j를 i개의 수로 나타내는 방법의 수'를 의미합니다.
2. 'j를 i개의 수로 나타내는 방법의 수'는 다음과 같습니다.
   'j를 i-1개의 수로 나타내는 방법의 수' + 'j-1을 i개의 수로 나타내는 방법의 수'
   
   예를 들어 4를 3개의 수로 나타내는 방법의 수는 다음과 같습니다.
   '4를 2개의 수로 나타내는 방법의 수' + '3을 3개의 수로 나타내는 방법의 수'
   
   'j를 i-1개의 수로 나타내는 방법의 수'에서 0을 추가하면 여전히 합은 그대로이면서 숫자의 개수는 1 증가합니다.
   마찬가지로, 'j-1을 i개의 수로 나타내는 방법의 수'에서 1을 추가하면 합은 1 증가하고 숫자의 개수는 그대로입니다.

이를 이용해 문제를 풀어보겠습니다.

1. 먼저, dp 배열을 초기화합니다. dp 배열의 크기는 (N+1) * (K+1)이며, 모든 값을 0으로 설정합니다.
2. dp[0][0] 값은 1로 설정합니다. 0을 0개의 수로 나타내려면 아무것도 선택하지 않으면 됩니다.
3. 이제 각 dp[j][i] 값을 계산합니다. dp[j][i] 값은 dp[j][i-1] 값과 dp[j-1][i] 값을 더한 것과 같습니다.
4. 마지막으로, dp[N][K] 값을 반환합니다. 이 값은 N을 K개의 수로 나타내는 방법의 수를 의미합니다.

e.g.

N = 4, K = 3 인 경우

dp 배열은 다음과 같습니다.

 

1	1	1	1
0	1	2	3
0	1	3	6
0	1	4	10
0	1	5	15

 

따라서 답은 15가 됩니다.