Python - [백준]2225-합분해

N을 K개의 수를 이용하여 합이 되는 경우를 찾는 문제이다.

접근방법

dp문제 답게 규칙성을 찾아보았다.

• k=1인경우, 모든 N에 대해 1이다.
• k = 2인 경우 , n+1이다.
• k = 3 인 경우, 1 + ... + n+1까지의 합이다. 이를 식으로 나타내면 1 + f(1,2), + f(2, 2)+ ...f(n, k-1)으로 나타낼 수 있다.
• k = 4 인 경우, 1 + 3 + 6 + 10 ..이다. 이를 또 식으로 나타내면 1 + f(1, 3) + f(2, 3)+ ... + f(n, k-1)로 나타낼 수 있다.

결국 점화식은, dp[n][k] = dp[1][k-1] + ... + dp[n][k-1]로 표현할 수 있다. 이것을 더 간단히 표현한다면 dp[n][k] = dp[n-1][k] + dp[n][k-1]로 표현할 수 있다(파스칼의 삼각형)

n, k = map(int, input().split())

dp = [[1 for i in range(k+1)] for i in range(n+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]
print(dp[n][k] % 1000000000)