[Python/파이썬] 백준 13707번 합분해 2

13707번: 합분해 2

 

문제

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

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

입력

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

출력

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

코드

n, k = map(int, input().split())
dp = [[0]*(k+1) for _ in range(n+1)]  # j개의 수로 i를 만드는 방법의 수
for i in range(n+1):
    dp[i][1] = 1    # 1개의 수로 i를 만드는 방법은 1개
for j in range(1, k+1):
    dp[0][j] = 1    # j개의 수로 0을 만드는 방법은 1개
for i in range(1, n+1):
    for j in range(2, k+1):
        dp[i][j] = (dp[i-1][j]+dp[i][j-1]) % 1_000_000_000
print(dp[n][k])

 

dp[i][j]에는 j개의 수로 숫자 i를 만드는 방법의 수를 저장한다.

1개의 수로 숫자 i를 만드는 방법은 i 본인 1개로 만드는 방법 1개뿐이다. 그리고 j개의 수로 0을 만드는 방법도 0을 j개 사용하는 방법 1개뿐이다. 이렇게 초기화를 해주고 반복문으로 dp 배열을 채워준다.

i-1을 j개의 수로 만드는 방법에서 1을 그 수들 중 하나에 더해주거나 i를 j-1개로 만드는 방법에 0을 1개 추가해서 숫자 i를 만들 수 있다. 따라서 점화식은 아래와 같다.$$dp[i][j] = dp[i-1][j]+dp[i][j-1]$$