[DP] 2225: 합분해

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

2225번: 합분해

 

1. 풀이

dp[i][j] : 정수 j개를 더해서 i가 되는 경우의 수

 

※ 이처럼 DP문제는 규칙을 찾는게 가장 중요하다.

 

2. 코드

from sys import *

# INPUT
N, K = map(int, stdin.readline().rstrip().split())

# DP
dp = [[0] * 201 for _ in range(201)]
for i in range(201):
    dp[i][1] = 1
for j in range(2, 201):
    dp[1][j] = j

for i in range(2, N + 1):
    for j in range(2, K + 1):
        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000

print(dp[N][K])