[Python] 백준 2225 합분해

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

2225번: 합분해

 

코드 작성

n, k = map(int, input().split())
dp = [[0]*201 for _ in range(201)]
for i in range(201):
    dp[1][i] = 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]
print(dp[k][n] % 1000000000)

코드  풀이

#1 초기값

 k = 1일 때, 즉 1자리수 일 때

 N은 그 자신의 수만 될 수 있으므로 1이 된다.

 또한, N이 1일때 k = 경우의 수가 된다.

 가령 k가 4 n이 1일경우

  (0,0,0,1), (0,0,1,0), (0,1,0,0), (1,0,0,0)

#2 점화식

 

dp[k][n] = dp[k-1][j] + dp[k][j-1]