[백준][Python] 13707 합분해 2

중복순열 문제이며 N개를 K칸에 분배하는 문제이다.

K칸에서 N-1개를 분배하는 경우에서 1개를 더 분배하는 모든 경우의 수(0인칸이 남는 경우의수가 배제됨)

N개를 K-1칸에 분배 하는 경우의 수에 0인칸을 하나씩 붙혀주는 경우의 수(위에서 배제된 경우의 수가 충족됨)

의 합을 구하는 문제.

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
dp = [[0]*5001 for _ in range(5001)]
# 결국 숫자1 N개를 K개의 칸에 분배하는 경우의 수.
# N-1개를 K개에 분배하는 경우의수에 1씩 더하는 경우 + N개를 K-1개에 분배하는 경우의수에서 0을 가지는 한칸을 더하는경우,
for i in range(1,N+1):
    for j in range(1,K+1):
        if i==1:
            dp[i][j] = j
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1])%1000000000
print(dp[N][K])