[골드5] 2225번 : 합분해

🛠 문제

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

👩🏻‍💻 해결 방법

규칙을 쉽게 생각해내지 못해서 어려웠던 문제다
예를 들어 n=2, k=3인 경우에는
(0을 1개의 숫자로 만드는 경우의 수 x 2를 2개의 숫자로 만드는 경우의 수)
+(1을 1개의 숫자로 만드는 경우의 수 x 1을 2개의 숫자로 만드는 경우의 수)
+(2를 1개의 숫자로 만드는 경우의 수 x 0을 2개의 숫자로 만드는 경우의 수)
로 모든 경우의 수를 구할 수 있다
따라서 table(n, k) = table(n, k-1) + table(n-1, k)의 점화식을 통해 답을 구할 수 있다

소스 코드

n, k = map(int, input().split())
dp = [[0] * 201 for _ in range(201)]  # dp[k][n]

for i in range(1, 201):
  dp[1][i] = 1  # k가 1일 때
  dp[2][i] = i + 1  # k가 2일 때

for i in range(2, 201):
  dp[i][1] = i  # n이 1일 때
  for j in range(2, 201):
    dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000000

print(dp[k][n])