문제

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

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

www.acmicpc.net/problem/2225

  • 입력

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

  • 출력

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

최종 코드

처음에는 갈피를 못잡고 헤매다가 친구의 도움을 받아 풀 수 있었다.

예를 들어 N = 5, K = 4인 경우 0 _ _ _ (N = 5, K = 3인 경우), 1 _ _ _ (N = 4, K = 3인 경우), 2 _ _ _ (N = 3, K = 3인 경우), 3 _ _ _ (N = 2, K = 3인 경우), 4 _ _ _ (N = 1, K = 3인 경우), 5 _ _ _ (N = 0, K = 3인 경우) 으로 나눠 생각할 수 있다.

이를 식으로 나타내면 dp[5][4] = dp[5][3] + dp[4][3] + dp[3][3] + dp[2][3] + dp[1][3] + dp[0][3] 이다.

하지만 여기서 dp[4][4] = dp[4][3] + dp[3][3] + dp[2][3] + dp[1][3] + dp[0][3] 이므로 식을 간략히 하면 dp[5][4] = dp[5][3] + dp[4][4] 가 된다.

이제 이를 점화식과 코드로 나타내보자!

dp[n][k] = dp[n][k-1] + dp[n-1][k]

import copy

n, k = map(int, input().split())
dp = [[x+1 for x in range(k)], [x+1 for x in range(k)]]

for i in range(1, n):
    for j in range(1, k):
        dp[1][j] = dp[0][j] + dp[1][j-1]
    dp[0] = copy.deepcopy(dp[1])

print(dp[1][-1]%1000000000)

처음에 dp를 dp = [[x+1 for x in range(k)], [0]*k]로 잘못 초기화하는 실수가 있었다.

ps하면서 가장 많이 실수가 나는 부분 중 하나가 n = 0 or 1 인 경우인 것 같다. 꼼꼼히 확인하는 습관을 기르자..!

참고 사이트