[백준 2225] 합분해
Tip
•
n = 1일 경우, 경우의 수는 k개
•
k = 1일 경우, 경우의 수는 자기자신 1개
•
k = 2일 경우, 경우의 수는 n + 1개
•
k, n이 2 이상인 경우, d[k][n] = d[k][n - 1] + d[k - 1][n]
풀이 소스 코드
import sys
si = sys.stdin.readline
# n, k 입력
n, k = map(int, si().split())
# DP 테이블
d = [[0] * 201 for i in range(201)]
for i in range(201):
d[1][i] = 1
d[2][i] = i + 1
for i in range(2, 201):
d[i][1] = i
for j in range(2, 201):
d[i][j] = (d[i][j - 1] + d[i - 1][j]) % 1000000000
print(d[k][n])
Python