[백준/Python3] 2225번 합분해

🧭Problem

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

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

Solution

K개의 수를 더해서 N을 만들 수 있는 방법을 출력하는 문제이다. for문을 K개 만큼 반복시킨다면 시간 복잡도가 K에 비례해서 복잡해진다. 하지만 다이나믹 프로그래밍을 이용하면 이전의 해를 이용해서 같은 계산을 여러번 하지 않고 해를 구할 수 있다.
먼저, K와 N의 상관관계를 생각해본다.
K가 1이면 모든 N의 경우의 수는 N개이다.
K가 2이면 N이 3일 때 경우의 수는 4개이다.

• (0 + 3), (1 + 2), (2 + 1), (3 + 0)

N이 4일 때는 5, 5일 때는 6이 된다. 따라서, K가 2일 때 합이 N이 되는 경우의 수는 N + 1개임을 알 수 있다.
K가 3이라면 N이 2일 때 6개, N이 3일 때 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

표를 보고 식을 도출하면 N > 1일 때 (N, K) = (N - 1, K) + (N, K - 1)이 된다는 것을 알 수 있다.

Python Code

from sys import stdin

MOD = 1000000000
N, K = map(int, stdin.readline().split())
dp = [[0] * (N + 1) for _ in range(K + 1)]
dp[0][0] = 1

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

print(dp[K][N])