[백준] 2225 - 합분해

1. 문제

2225번: 합분해

2. 개요

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

3. 풀이 및 코드

3-1. 풀이

사용할 수의 개수 K와 만들 수 N을 각각 행, 열로 하는 표를 만들어보자.

	0	1	2	3	4	5
1
2
3
4

먼저 K = 1일때, 수 하나로 해당 수를 만드는 경우는 자기 자신 하나뿐이므로 1을 채워넣는다.

또한 합이 0이 되는 경우도 0이 자기 자신 하나만을 사용하는 경우이므로 1을 채워넣는다.

	0	1	2	3	4	5
1	1	1	1	1	1	1
2	1
3	1
4	1

K = 2인 경우를 생각해보자.

N = 1 → 1 + 0, 0 + 1 2개, N = 2 → 2 + 0, 1 + 1, 0 + 2 3개, N = 3 → 3 + 0, 1 + 2, 2 + 1, 0 + 3 4개 …

1씩 늘어나게 된다.

	0	1	2	3	4	5
1	1	1	1	1	1	1
2	1	2	3	4	5	6
3	1
4	1

K = 3일때, 여기서 잠깐 지난 값과의 관계에 대해 짚고 넘어가보자.

N = 1인 경우 → (수 2개로 0을 만든 경우 + 1) + (수 2개로 1을 만든 경우 + 0) 이다.

N = 2인 경우 → (수 2개로 0을 만든 경우 + 2) + (수 2개로 1을 만든 경우 + 1) + (수 3개로 2를 만든 경우 + 0) 이다.

즉 dp의 점화식이 dp[i][j] = dp[i-1][0] + dp[i-1][1] + … dp[i-1][j]임을 알 수 있게 된다.

표를 채워넣으면 다음과 같아진다.

	0	1	2	3	4	5
1	1	1	1	1	1	1
2	1	2	3	4	5	6
3	1	3	6	10	15	21
4	1	4	10	20	35	56

여기서 또 한가지 규칙이 있는데

dp[i][j] = dp[i-1][j] + dp[i][j-1] 또한 성립한다는 것을 알 수 있다.

dp[i][j-1] = dp[i-1][0] + dp[i-1][1] + … dp[i-1][j-1] 이기 때문이다.

위를 활용해 코드를 작성한다.

3-2. Python

import sys

N, K = map(int, sys.stdin.readline().split())

dp = [[0 for i in range(N+1)] for j in range(K+1)]

for i in range(K+1):
    for j in range(N+1):
        if i == 0:
            continue
        
        if i == 1:
            dp[i][j] = 1

        elif j == 0:
            dp[i][j] = 1

        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000000

print(dp[-1][-1])

3-3. C#

static void Main(string[] args)
{
    string[] input = Console.ReadLine().Split();

    int N = int.Parse(input[0]);
    int K = int.Parse(input[1]);

    long[,] dp = new long[K+1, N+1];

    for (int i = 0; i < K + 1; i++)
    {
        for (int j = 0; j < N + 1; j++)
        {
            if (i == 0)
                continue;

            if (i == 1 || j == 0)
                dp[i, j] = 1;

            else
                dp[i, j] = (dp[i - 1, j] + dp[i, j - 1]) % 1000000000;
        }
    }

    Console.WriteLine(dp[K,N]);
}