[백준/Python] 2225 합분해

문제 링크

2225번: 합분해

 

문제 풀이

• 0~N의 수를 k만큼 사용해서 N을 만드는 경우의 수를 구하는 문제이다.
• 주어진 예제의 N=6, k=4인 경우를 살펴보면 다음과 같이 표를 작성할 수 있다.

k \ N	0	1	2	3	4	5	6
1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7
3	1	3	6	10	15	21	28
4	1	4	10	20	35	56	84

• 이를 점화식으로 표현하면 다음과 같다.
  • dp[k][N] = dp[k-1][N] + dp[k-1][N-1] + ... + dp[k-1][0]

 

전체 코드

import sys

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

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

print(dp[-1][-1] % 1000000000)