[BOJ] 백준 2225 합분해 Python

2225번: 합분해

문제풀이
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 전형적인 DP문제이다. 
먼저 DP배열을 2차원 배열로 초기화해서 선언하고 그 안을 점화식으로 채워넣는 방식의 논리를 사용했다.
1. K가 1일때는 수 하나로 N을 표시해야하므로 경우의 수는 반드시 1개이다. 
2. N이 1일때는 K-1개의 0과 1개의 1이 필요하므로 경우의 수는 K의 증가율과 같이 증가한다.
3. 여기서 예시를 직접 쓰다가 점화식을 찾았다. 
점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1]
개념적으로 생각했을때 당연하게도 다음수까지의 경우의 수를 구하려면 이전 수까지의 경우의 수를 알아야한다.
예시가 K==6 , N == 4 일때 풀이는 아래의 그림과 같다.

---

Code

from sys import stdin

input = stdin.readline
mod = 1000000000


def solve():
    N, K = map(int, input().split())
    dp = [[0] * (200 + 1) for _ in range(200 + 1)]
    for i in range(201):
        dp[1][i] = 1
        dp[i][1] = i
    for i in range(2, 201):
        for j in range(2, 201):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    print(dp[K][N] % mod)


solve()