[BOJ 13707 🥇4] 합분해 2 (Python)

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

13707번: 합분해 2

문제

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

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

입력

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

출력

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

예제 입력 1

20 2

예제 출력 1

21

 

⭕ CODE

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

# d[i][j] -> j개 사용해서 i를 만드는 경우의 수
d = [[0]*(5001) for _ in range(5001)]

# 0개 사용해서 0을 만드는 방법은 무조건 1개 이므로
d[0][0] = 1

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

✏️ Comment

	n=1	2	3	4	5	6	7	8
k = 1	1	1	1	1	1	1	1	1
k = 2	2	3	4	5
3	3	6	10
4	4
5	5

k가 1인 경우는 1가지 숫자만 사용하여서 n을 만들기 때문에 모든 d[i][k] = 1
n이 1인 경우는 k가지 숫자를 사용하여 n을 만들기 때문에 k=2 (1,0), (0,1) 2개, k=3 (1,0,0),(0,1,0),(0,0,1) 3개 즉 k개 

n=2 k=2 -> (1,1),(2,0)(0,2), n=3 k=2 -> (1,2)(2,1)(3,0)(0,3), n=4 k =2 -> (0,4)(4,0),(1,3)(3,1)(2,2) 등등 이런식으로 채워가다보면
k가 3인 경우도 보면 n=2 k=3 -> (0,0,2) 3 가지 (0,1,1) 3가지 -> 총 6가지 n=3 k=3 -> (3,0,0) 3가지 (1,1,1) 1가지 (1,2,0) 6가지 총 10가지
d[n][k] = d[n-1][k] + d[n][k-1] 이라는 점화식을 만들 수 있다.