백준알고리즘 - 2225번 합분해 - 파이썬(Python)

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

 

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

 

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

예제 입력과 출력

 

 

알고리즘 분류

다이나믹 프로그래밍 

 

정답

 

import sys
input= lambda : sys.stdin.readline().strip()

n,k=map(int,input().split())

dp=[[0]*201 for i in range(201)]

for i in range(201):
    dp[1][i]=1
    dp[2][i]=i+1

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

print(dp[k][n])

n과 k의 관계에 대해 생각해보았습니다.

 

k에 상관없이 n이 1인 경우에 합이 n이 되는 경우의 수는 k개입니다.

ex) k = 2 이고 n = 1 이면 (0, 1) (1, 0) 2개

ex) k = 4 이고 n = 1 이면 (0, 0, 0, 1) (0, 0, 1, 0) (0, 1, 0, 0) (1, 0, 0, 0) 4개

 

k = 1 이면 n에 상관없이 합이 n이 되는 경우의 수는 1개입니다. (n 자신 1개)

 

k = 2 이면

위의 예제에서처럼 n = 20 이면 21개입니다.

(10,10) 1개와

(0, 20) (1, 19) (2, 18) (3, 17) (4, 16) (5, 15) (6, 14) (7, 13) (8, 12) (9, 11) 10가지를 순서 바뀐 경우로 20가지

20 + 1 = 21

n = 3 이면 (3, 0) (1, 2) 2가지를 순서 바뀐 경우로 4가지, 총 4가지입니다.

이를 통해 k = 2 이면 합이 n이 되는 경우의 수는 n+1개입니다.

 

k = 3 이면

n = 2 일 때 (0, 1, 1) (1, 1, 0) (1, 0, 1) (0, 0, 2) (0, 2, 0) (2, 0, 0) 6개입니다.

n = 3 일 때 (0, 0, 3) (0, 3, 0) (3, 0, 0) (0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0) (1, 1, 1) 10개입니다.

 

이를 표로 표현하면 다음과 같습니다.

	n = 1	n = 2	n = 3	n = 4	n = 5	...
k = 1	1	1	1	1	1	...
k = 2	2	3	4	5	6	...
k = 3	3	6	10	15	21	...

이를 통해 점화식 dp[i][j] = dp[i][j-1]+dp[i-1][j] (i, j가 2 이상인 경우) 를 도출할 수 있습니다. 

 

---

백준 알고리즘 2225번 : https://www.acmicpc.net/problem/2225

2225번: 합분해