BOJ - 합분해(2225)

골드5 : 동적계획법 문제이다.

풀이

잘 접근했다고 생각했는데, 점화식을 잘 못 구했다. 나중에 다시 제대로 이해하고 적을 것

Code

from pprint import pprint
 
n, k = map(int, input().split())
dp = [[0 for _ in range(n + 1)] for _ in range(k + 1)]
mod = int(1e9)
for i in range(n + 1):
    dp[1][i] = 1
 
 
for i in range(2, k + 1):
    for j in range(n + 1):
        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod
 
print(dp[k][n] % mod)
 

Reference

• 백준(2225번) - 합분해