| 시간 제한 | 메모리 제한 |
| 2초 | 128 MB |
문제
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
풀이
일단 K개의 정수로 N을 만들어냈을 때, K - 1개의 정수로 N - a 를 만든 것과 1개의 정수로 a를 만든 경우의 합과 같다는 것을 알았다. 부분 해를 합해 전체 해를 얻을 수 있으므로 DP를 쓰는 문제인 건 확실하다.
문제는 점화식이 어떻게 되는 건지 정리가 너무 어렵다는 것이다. 그래서 N과 K의 값에 따라 얻어지는 해를 좀 수작업으로 구해보기로 했다.
| N\K | 0 | 1 | 2 | 3 | 4 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 1 | 3 | 6 | 10 |
| 3 | 0 | 1 | 4 | 10 | 20 |
| 4 | 0 | 1 | 5 | 15 | 35 |
| 5 | 0 | 1 | 6 | 21 | 56 |
... 왜인지 모르겠지만 누적합이 나오는 걸 확인할 수 있었다. N과 K가 주어졌을 때 해를 dp[N][K]라고 하면 점화식을 이렇게 쓸 수 있다는 소리다.
dp[N][K] = dp[N - 1][K] + dp[N][K - 1]
왜 되는 거지..?
원리는 1도 이해가 안되고 있지만 귀납적으로 어쨌든 찾아야 할 규칙은 파악해냈다. 허허
정답 코드
더보기
N, K = map(int, input().split())
dp = [[0 for j in range(K + 1)] for i in range(N)]
for i in range(K + 1):
dp[0][i] = i
for i in range(1, N):
for j in range(1, K + 1):
dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
if dp[i][j] > 1000000000:
dp[i][j] -= 1000000000
print(dp[N - 1][K])
