BOJ 2225 합분해

https://www.acmicpc.net/problem/2225
시간 2초, 메모리 128MB
input :

• N K(1 ≤ N, K ≤ 200)

output :

• 답을 1,000,000,000으로 나눈 나머지를 출력

조건 :

• 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수
• 덧셈의 순서가 바뀐 경우는 다른 경우, 한 개의 수를 여러 번 쓸 수도

그래서 N = 4, K = 4를 구하려면.
dp[0 ~ N][K - 1]의 합을 구하자.

import sys

n, k = map(int, sys.stdin.readline().split())
dp = [[1] * 201 for i in range(201)]

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


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