💡 문제
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
💭 접근
우선 예를 들어 보면,
ex) n = 3, k = 3
0 0 3
0 1 2
0 2 1
0 3 0
-----> (n = 3, k = 2) 경우의 수 = 4
1 0 2
1 1 1
1 2 0
-----> (n = 2, k = 2) 경우의 수 = 3
2 0 1
2 1 0
-----> (n = 1, k = 2) 경우의 수 = 2
3 0 0
-----> (n = 0, k = 2) 경우의 수 = 1
총 10개의 경우의 수를 가진다.
위의 예시를 보았을 때 dp[k][n]이 dp[3][3]이라고 했을때,
dp[3][3] = dp[2][3] + dp[2][2] + dp[2][1] + dp[2][0] 인 것을 볼 수 있다.
이를 일반화하면,
dp[k][n] = dp[k - 1][0] + dp[k - 1][1] + ... + dp[k - 1][n] 이다.
이때, dp[k][n - 1] = dp[k - 1][0] + ... + dp[k - 1][n - 1] 이므로,
최종적으로 점화식은 dp[k][n] = dp[k][n - 1] + dp[k - 1][n]으로 나타낼 수 있다.
이를 표로 나타내면,
| n=1 | n=2 | n=3 | n=4 | n=5 | n=6 | ... | |
|---|---|---|---|---|---|---|---|
| k=1 | 1 | 1 | 1 | 1 | 1 | 1 | ... |
| k=2 | 2 | 3 | 4 | 5 | 6 | 7 | ... |
| k=3 | 3 | 6 | 10 | 15 | 21 | 28 | ... |
| k=4 | 4 | 10 | 20 | 35 | 56 | 84 | ... |
이와 같이 직관적으로 볼 수 있다.
📒 코드
n, k = map(int, input().split())
dp = [[0 for _ in range(n + 1)] for _ in range(k + 1)]
for i in range(1, k + 1):
dp[i][1] = i
for j in range(2, n + 1):
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000000
print(dp[k][n] % 1000000000)💭 후기
점화식의 패턴을 완벽하게 파악하고 유도하는 과정이 매우 까다로웠던 문제이다.
🔗 문제 출처
https://www.acmicpc.net/problem/2225
