[백준][2225] 합분해

• Problem Link : https://www.acmicpc.net/problem/2225

---

문제

• 0부터 N까지의 정수 k개를 더해서 그 합이 N이 되는 경우의 수를 구하라.
• 덧셈의 순서가 바뀐 경우는 다른 경우로 센다.
• 동일한 수를 여러 번 쓸 수도 있다.

입력

• 첫째 줄, 두 정수 N, K가 주어진다.

출력

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

---

풀이

실제로 경우의 수를 측정하면 그 수가 굉장히 많아진다. N과 K가 200까지 입력이 들어올 수 있기 때문에 일일히 확인하면 당연하게도 실행 시간 초과 문제가 발생할 것이기 때문에 이렇게 큰 수의 결과가 나오는 문제의 경우에는 점화식을 만들어서 해결할 수 있다. 변수간 어떤 관계가 성립하는지를 살펴보면 쉽게 점화식을 구할 수 있다.

이 문제에서는 두 정수 N과 K를 주기 때문에 N과 K의 관계를 살펴보자.

n을 k개로 나누는 경우의 수는 (0, [n을 k-1]개로 나눈 것) + (1, [n-1을 k-1]개로 나눈것), ··· , (n, [0을 k-1]개로 나눈 것) 이다.

• 따라서, 점화식으로 표현하면 아래와 같다
  $dp[n][k] = dp[0][k-1] + dp[1][k-1] + ··· + dp[n-1][k-1] + dp[n][k-1]$
• 이 때 n-1를 k개로 나누는 점화식은 아래와 같다.
  $dp[n-1][k] = dp[0][k-1] + dp[1][k-1] + ··· + dp[n-1][k-1]$
• 따라서, 첫 번째 식을 다음과 같이 정리할 수 있다.
  $dp[n][k] = dp[n-1][k] + dp[n][k-1]$

이 때 k=1일때와 k=2일때의 n 값은 쉽게 구할 수 있다.

• k = 1일때는 n에 상관없이 무조건 경우의 수가 1이다.
• k = 2일떄는 (n, 0), (n - 1, 1), ··· , (0, n)이므로 경우의 수가 n+1이다.

---	n = 1	n = 2	n = 3	n = 4	n = 5	···
k = 1	1	1	1	1	1	···
k = 2	2	3	4	5	6	···
k = 3	3	6	10	15	21	···
k = 4	4	10	20	35	56	···

와 같이 표를 구할 수 있고 문제에서 요구하는 n을 k로 나누는 경우의 수를 계산할 수 있다.

---

코드

import sys

input = sys.stdin.readline

n, k = map(int, input().split())

dp = [[0] * 201 for i in range(201)]

# k=1, 2일 때는 바로 대입
for i in range(201):
    dp[1][i] = 1
    dp[2][i] = i + 1

for i in range(2, 201):
    # n = 1일때는 k로 나눌 때 1의 위치만 k개로 바뀌기 때문에 바로 계산 가능
    dp[i][1] = i
    for j in range(2, 201):
        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000

print(dp[k][n])