BaekJoon Online Judge 2225번

문제 링크

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

2225번: 합분해

k = 1 이면, 경우는 자기 자신밖에 없으므로 경우의 수는 모두 1이다.

1,2 -> 01 10   2가지
2,2 -> 02 11 20  3가지
3,2 -> 03 12 21 30   4가지
4,2 -> 04 13 22 31 40  5가지
5,2 -> 05 14 23 32 41 50   6가지

이처럼 k = 2 이면, 경우의 수는 n + 1 이 된다. 1,3 -> 001 010 100  3가지
2,3 -> 002 020 200 011 101 110  6가지
3,3 -> 003 030 300 111 120 102 210 201 021 012  10가지

이를 토대로 표를 작성하면,

이렇게 된다.
표를 살펴보면, (3 , 1) + (2, 2) = (3, 2) 가 되는 것 처럼 (k, n) = (k-1, n) + (k, n-1)이 되는 규칙이 다른 부분에서도 성립한다는 것을 알 수 있다.  

number, times = map(int,input().split()) #number는 n, times는 k이다.

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

for i in range(201):
  dp[1][i] = 1 #time가 1일 때, 경우의 수가 모두 1인것.
  dp[2][i] = i+1 #time가 2일 때, 경우의 수가 n+1이 되는 것.

for i in range(2,201):
  dp[i][1] = i
  for j in range(2,201):
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
result = dp[times][number] % 1000000000
print(result)