[Python] 백준 2225번 : 합분해

문제

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

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

입력

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

출력

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

예제 입력 1

20 2

예제 출력 1

21

예제 입력 2

6 4

예제 출력 2

84

 

소스코드

INF = 1e9

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

if k > 1:
    for i in range(1, n+1):
        dp[2][i] = i+1

for i in range(2, k+1):
    dp[i][1] = i
for i in range(3, k+1):
    for j in range(2, n+1):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % INF

print(int(dp[k][n]))

몇 가지 경우의 수를 통해 점화식을 구해보면 아래와 같다는 것을 알 수 있다.

 

k = 1 : dp[1][n] = 1

k = 2 : dp[2][n] = n+1

k >= 3 : dp[k][n] = dp[k-1][n] + dp[k][n-1]

 

위 점화식을 코드로 구현하면 되는 문제였다.

그런데 모듈러 처리 문제로 인해 오답이 발생했었다. 모듈러 처리를 마지막 print문 안에 해주었더니 오답이 나와서 이중 for문 안으로 옮겨주었고, 모듈러 처리 결과가 실수로 출력되어서 int형으로 변환도 해주었다.

dp[2][i] 값을 설정할 때, 입력받은 k 값이 2 이상인지 확인하는 것도 유의해야 한다.