백준 2225 : 합분해 - javascript(dp)

문제 출처 

https://www.acmicpc.net/problem/2225

 

정답 풀이 

핵심 아이디어:

dp[k][n]은 K개의 수로 N을 만드는 방법의 수를 의미합니다. 이를 구하기 위해서, 두 가지 상황을 고려합니다:

1. dp[k][n-1]: K개의 수로 N-1을 만드는 경우에, 추가로 1을 더한 경우입니다. 즉, N을 만들기 위해 마지막에 1을 추가하는 방법입니다.
2. dp[k-1][n]: K-1개의 수로 N을 만드는 경우에, 추가로 0을 하나 추가하는 방법입니다. 즉, N을 만들기 위해 마지막 수로 0을 더하는 방법입니다.

이 두 가지를 더하면 dp[k][n]이 구해집니다.

예시:

N = 5, K = 3인 경우를 생각해보겠습니다. 즉, 숫자 5를 3개의 숫자의 합으로 나타내는 경우의 수를 구하는 문제입니다.

1. dp[3][5] = dp[3][4] + dp[2][5]

• dp[3][4]: 숫자 4를 3개의 숫자의 합으로 나타내는 방법의 수입니다. 여기에 1을 더하면 숫자 5를 만들 수 있습니다.
  • 예를 들어, 4를 3개의 숫자로 만드는 방법이 1 + 2 + 1이었다면, 이 방법에 1을 추가하면 1 + 2 + 2로 5를 만들 수 있습니다.
• dp[2][5]: 숫자 5를 2개의 숫자의 합으로 만드는 방법의 수입니다. 여기에 0을 하나 추가하면 숫자 5를 만들 수 있습니다.
  • 예를 들어, 5를 2개의 숫자로 만드는 방법이 2 + 3이었다면, 여기에 0을 추가하여 2 + 3 + 0으로 5를 만들 수 있습니다.

2. 구체적인 수식 적용

• dp[3][4]: 4를 3개의 숫자의 합으로 나타내는 경우는 다음과 같습니다:
  • (0, 0, 4)
  • (0, 1, 3)
  • (0, 2, 2)
  • (0, 3, 1)
  • (1, 1, 2)
  • (1, 2, 1)
  • (2, 1, 1)
• 여기에 각각 1을 더하면 5를 3개의 숫자의 합으로 나타낼 수 있는 경우가 됩니다:
  • (0, 0, 5)
  • (0, 1, 4)
  • (0, 2, 3)
  • (0, 3, 2)
  • (1, 1, 3)
  • (1, 2, 2)
  • (2, 1, 2)
• dp[2][5]: 5를 2개의 숫자의 합으로 나타내는 경우는 다음과 같습니다:
  • (0, 5)
  • (1, 4)
  • (2, 3)
  • (3, 2)
  • (4, 1)
  • (5, 0)
• 여기에 각각 0을 더하면 5를 3개의 숫자의 합으로 나타낼 수 있는 경우가 됩니다:
  • (0, 5, 0)
  • (1, 4, 0)
  • (2, 3, 0)
  • (3, 2, 0)
  • (4, 1, 0)
  • (5, 0, 0)

총 정리:

따라서, dp[3][5]는 두 가지 방법의 합이 됩니다:

• dp[3][4]에서 1을 더한 경우
• dp[2][5]에서 0을 더한 경우

이 두 가지를 더하면, dp[3][5]는 dp[3][4]와 dp[2][5]의 값을 더한 값으로 계산됩니다. 이는 각 경우의 수를 나누어서 생각한 결과입니다.

일반화:

• dp[k][n] = dp[k][n-1] + dp[k-1][n]
  • dp[k][n-1]: 마지막에 1을 추가하여 N을 만드는 방법
  • dp[k-1][n]: 마지막에 0을 추가하여 N을 만드는 방법

이렇게 점화식을 통해 각 경우의 수를 효율적으로 계산할 수 있습니다.

정답 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n, k] = input[0].split(' ').map(v => +v); 

function solution(n, k) {
    const MOD = 1000000000;
    let dp = Array.from({ length: k + 1 }, () => new Array(n + 1).fill(0));

    for (let i = 0; i <= n; i++) {
        dp[1][i] = 1;  // 1개의 수로 n을 만드는 경우는 항상 1가지 (n 자신)
    }

    for (let i = 2; i <= k; i++) { // k개의 숫자로
        for (let j = 0; j <= n; j++) { // 합이 j인 경우
            for (let x = 0; x <= j; x++) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % MOD;
            }
        }
    }

    return dp[k][n];
}

console.log(solution(n, k));

 

추가 해설 

dp[k][n] = (dp[k][n] + dp[k - 1][n - x]) % MOD; 부분이 이해되지 않는다고 하셨는데, 이 부분을 좀 더 구체적으로 설명해 드리겠습니다.

dp[k][n]의 의미:

• dp[k][n]은 N을 K개의 수의 합으로 나타내는 경우의 수를 의미합니다.
• 예를 들어, dp[3][5]는 "숫자 5를 3개의 수로 나타내는 방법의 수"를 의미합니다.

핵심 아이디어:

이 문제에서 dp[k][n]을 구하기 위해서는 이전에 구한 값들을 기반으로 새로운 값을 구합니다. 즉, k-1개의 수로 n-x를 만들 수 있는 모든 경우에 추가로 x를 더해 k개의 수로 n을 만들 수 있다는 개념입니다.

식의 해석:

dp[k][n] = (dp[k][n] + dp[k - 1][n - x]) % MOD;

이 식을 해석해 보면:

1. dp[k][n]: 현재까지 계산된 "숫자 n을 k개의 수로 나타내는 방법"의 수입니다.
2. dp[k - 1][n - x]: 숫자 n-x를 k-1개의 수로 나타내는 방법의 수입니다. 이 값은 k-1개의 수로 n-x를 만들고, 거기에 x를 더해서 n을 만드는 경우를 의미합니다.
   • 예를 들어, k-1개의 수로 n-x를 만들 수 있다면, 그 값에 x를 추가하여 k개의 수로 n을 만들 수 있습니다.

구체적인 예시:

예를 들어, N = 5, K = 3일 때를 가정해 봅시다. 즉, 숫자 5를 3개의 숫자의 합으로 나타내는 경우의 수를 구하려고 합니다.

1. dp[3][5] = dp[3][5] + dp[2][5 - x]

이때, x는 0부터 n까지 가능한 모든 값을 탐색합니다. 여기서 x는 마지막에 더해지는 숫자입니다.

• x = 0인 경우:
  • dp[2][5 - 0] = dp[2][5]: 2개의 수로 5를 만드는 경우에 0을 추가한 것.
• x = 1인 경우:
  • dp[2][5 - 1] = dp[2][4]: 2개의 수로 4를 만드는 경우에 1을 추가한 것.
• x = 2인 경우:
  • dp[2][5 - 2] = dp[2][3]: 2개의 수로 3을 만드는 경우에 2를 추가한 것.
• x = 3인 경우:
  • dp[2][5 - 3] = dp[2][2]: 2개의 수로 2를 만드는 경우에 3을 추가한 것.
• x = 4인 경우:
  • dp[2][5 - 4] = dp[2][1]: 2개의 수로 1을 만드는 경우에 4를 추가한 것.
• x = 5인 경우:
  • dp[2][5 - 5] = dp[2][0]: 2개의 수로 0을 만드는 경우에 5를 추가한 것.

2. 이 계산을 통해:

우리는 모든 가능한 값을 x에 대해 계산하여 dp[k][n]에 더해줍니다.

왜 여러 값을 더하는가?

이는 중복되는 경우의 수를 모두 고려하기 위해서입니다. 예를 들어, 숫자 5를 3개의 수로 나타내는 방법은 여러 가지가 있습니다:

• (0 + 5 + 0)
• (1 + 3 + 1)
• (2 + 2 + 1) 등등...

이런 식으로, 다양한 숫자를 통해 모든 가능한 조합을 찾기 위해서 x값을 0부터 n까지 모두 더해주어야 합니다.

요약:

• dp[k][n] = (dp[k][n] + dp[k-1][n-x]) % MOD;는 k개의 수로 n을 만드는 방법은, 마지막에 x를 추가하는 방법을 고려한 것.
• dp[k-1][n-x]는 k-1개의 수로 n-x를 만드는 방법의 수입니다.
• 이 식을 사용해서 숫자 N을 K개의 수로 나타내는 경우의 수를 구할 수 있습니다.