백준 C# - 2225 +) 풀이

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다.

여기서 중요한 부분은 "0"부터 포함된다는 것이다. 그러므로 정수 1개로 0을 만드는 경우의 수도 1가지 존재한다.

 

k = 사용할 정수의 개수

n = 목표 합계

 

점화식 생각

1. dp[k,n] 배열에 어떤 값을 넣을까?

dp[k,n] = 정수 k개로 합이 n이 되는 경우의 수이다.

2.  i를 만들기 위해 바로 전 단계는 뭘까?

1) 마지막 수가 0인 경우 

2) 마지막 수가 1이상인 경우

---

점화식

dp[k,n] = dp[k-1,n] + dp[k,n-1];

1) dp[k-1,n]

정수 k개 중 하나가 0일때 나머지 k-1개로 n을 만들어야한다.

2) dp[k,n-1]

합이 n이 되도록 정수 k개를 만드려면 합이 n-1인 경우에 +1씩 해서 n을 만드는 경우

 

dp[2,2] 을 구한다고 하면

// 가능한 조합: (0, 2) (1, 1) (2, 0) → 총 3가지
dp[2,2] = dp[1,2] + dp[2,1]
        =     1   +    2
        =     3

 

 

dp문제는 그냥 손으로 직접 쓰고 패턴 구하는게 제일 좋은 것 같다!

---

코드 전문

using System;

class Solution
{
    static void Main()
    {
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        int n = input[0];
        int k = input[1];

        int[,] dp = new int[k+1, n+1];

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

        for (int i = 1; i <= k; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i, j] = (dp[i - 1, j] + dp[i, j - 1]) % 1000000000;
            }
        }

        Console.WriteLine(dp[k,n]% 1000000000);
    }
}