문제

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

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

아이디어

k=1인 경우,
경우의 수는 n의 값과 상관없이 모두 1

k=2인 경우,
경우의 수는 n+1

ex)n=4이면,
(0, 4)(1, 3)(2, 2)(3, 1)(4, 0) => 5개

k>=3인 경우,
우선 k=2이 경우와 같이 두 개로 자른 후 k값에 따라 다시 자른다.

ex)n=4, k=3이면,
(0, 4)(1, 3)(2, 2)(3, 1)(4, 0)에서 뒤의 숫자만 다시 두 개로 자른다.
(0, 4) => 4를 두 개로 자른다 => data(4,2)=5
(1, 3) => 3을 두 개로 자른다 => data(3,2)=4
(2, 2) => 2를 두 개로 자른다 => data(2,2)=3
(3, 1) => 1을 두 개로 자른다 => data(1,2)=2
(4, 0) => 0을 두 개로 자른다 => data(0,2)=1
==>data(4,2)+data(3,2)+data(2,2)+data(1,2)+data(0,2)
==>5+4+3+2+1=15개

표로 표현하면 다음과 같다

k, n	0	1	2	3	4	5
1	1	1	1	1	1	1
2	1	2	3	4	5	6
3	1	3	6	10	15	21

data(n,k)=data(n,k-1)+data(n-1,k-1)+data(n-2,k-1)+...+data(0,k-1)
data(n-1,k)=data(n-1,k-1)+data(n-2,k-1)+data(n-3,k-1)+...+data(0,k-1)
==>data(n,k)=data(n,k-1)+data(n-1,k)

내 코드(Python) Error

((n+1)(n+2))/2가 계속 반복되는데 하나씩 조건을 추가하다가 이상해짐

import sys
input = lambda: sys.stdin.readline()

def findNum(num, k):
    cnt = 0
    if k == 2:
        cnt += num+1
    elif k == 3:
        cnt += ((num+1)*(num+2))/2
    else:
        for j in range(0,num+1):
            cnt += ((j+1)*(j+2))/2
        k -= 1
        if k != 3:
            cnt += findNum(num, k)
    return cnt

n, k = map(int, input().split())
cnt = 0
if k == 1:
    cnt = 1
else:
    cnt = findNum(n, k)
print(int(cnt))

다른 코드(Python)

import sys
input = lambda: sys.stdin.readline()

n, k = map(int, input().split())
data=[1]
data += [0]*n

for i in range(1,k+1):
    for j in range(1, n+1):
        data[j]=(data[j]+data[j-1])%1000000000
print(data[n])

출처 : https://suri78.tistory.com/105