[BOJ][python] 2225. 합분해

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

2225번: 합분해

---

💡IDEA

동적 계획법을 사용하는 문제이다.

규칙을 찾기 위해서는 직접 계산해보면서 찾는 것이 빠르다.

K \ N	1	2	3	4	5
1	1	1	1	1	1
2	2	3	4	5	6
3	3	6	10	15	21
4	4	10	20	35	56
5	5	15	35	70	126

위의 표 처럼 K와 N 값에 따른 0부터 N까지 정수 K개를 중복 허용하여 더해서 N이 되는 경우의 수를 계산할 수 있다.

K=1인 경우, 정수를 한 개만 사용해서 N을 만드는 경우는 N 한 경우 뿐이므로 모두 1이다.

N=1인 경우, 정수 K개로 1을 만드는 경우는 1+0×(K-1) 경우 뿐이고, 순서까지 고려해서 K개이다.

그 이후로는 전 행의 값과 전 열의 값을 더한 값이 현재 값이 된다는 규칙을 알 수 있다.

과정에서 1000000000을 나누고 남은 나머지를 더해주는 것을 주의하자.

마지막 열, 마지막 행에 최종 경우의 수를 구할 수 있다. 이 때도 1000000000을 나누고 남은 나머지를 출력한다.

 

📌CODE

N, K = map(int, input().split())
dp = [[0]*N for _ in range(K)]
dp[0] = [1]*N

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