[백준] 2225번 합분해 (by Python)

문제

0 이상 N 이하의 정수 K개를 더해 N을 만든다고 할 때, K가 1이면 N이 어떤 수든 방법은 1가지이다.

이러한 리스트를 dp_k로 나타낸다고 하면 dp_1은 길이가 n인 [1, 1, 1, 1 ...] 의 모습을 하고 있을 것이다.

그리고 2 이상의 k에 대해서는 dp_k[i] = sum(dp[:i + 1])이다.

 

풀이

n, k = map(int, input().split())

dp = [1] * (n + 1)
k -= 1

while k:
    next_dp = [1] * (n + 1)
    for i in range(1, n + 1):
        next_dp[i] = sum(dp[:i + 1])
    dp = next_dp[:]
    k -= 1

print(dp[-1] % 1000000000)