[백준] 2225 합분해 in Python <점화식을 테이블을 그리면 쉽게 구하는 DP문제>

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

2225번: 합분해

 

짜잔 이렇게 dp 테이블을 그려서 

dp[i][j] = dp[i-1][j] + dp[i][j-1] 라는 점화식을 도출해내면 끝이다 

단 i -1 > 0, j -1> 0 이어야 하므로 i, j 는 각각 2이상이어야 한다 !! 

그러기 위해서는 dp[?][1] 은 n (자기자신) 값으로 초기화 해주어야 하고 

dp[1][?] 는 1로 초기화해주어야 한다 

 

# 2225 합분해

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

for i in range(2, 201):
    for j in range(2, 201):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]


print(dp[k][n]%1000000000)