[ 2225 ] [ DP ] 합분해

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

2225번: 합분해

---

풀이 과정

---

1. 1차원 DP로도 풀 수 있겠지만, 2차원 DP로 풀이하는 편이 훨씬 직관적이고 보기 편하다.
2. DP[i][j]를 j개의 숫자를 써서 i를 만드는 경우의 수라고 할 때,
   1. DP[i][j]의 값은 DP[i][j-1]~DP[0][j-1]의 합과 같다.
   2. DP[i][j-1]의 케이스에서 숫자 0을 사이사이에 더해주면 되고, 비슷하게 DP[i-1][j-1]의 경우는 숫자 1, ... 숫자 i를 더해줄 때는 DP[0][j-1]이므로 (1)과 같다.
   3. DP[i][j]를 구하고 나서 나머지 연산을 같이 해주어야 속도가 빨라진다.
3. DP[N][M]을 출력시켜준다.

DP 점화식 고민할 때 너무 문제를 크게 잡고 고민하지 말고 작게 고민해야 함.. ㅜㅜ

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
dp = [[0] * (M+1) for i in range(N+1)]

for i in range(M+1):
    dp[0][i] = 1

for i in range(1, N+1):
    for j in range(1, M+1):
        for k in range(0, i+1):
            dp[i][j] += dp[k][j-1]
        dp[i][j] = dp[i][j] % 1000000000

print(dp[N][M])