2225
-
[백준] 2225번 합분해 (by Python)Programming/Algorithm 2021. 2. 28. 17:34
문제 0 이상 N 이하의 정수 K개를 더해 N을 만든다고 할 때, K가 1이면 N이 어떤 수든 방법은 1가지이다. 이러한 리스트를 dp_k로 나타낸다고 하면 dp_1은 길이가 n인 [1, 1, 1, 1 ...] 의 모습을 하고 있을 것이다. 그리고 2 이상의 k에 대해서는 dp_k[i] = sum(dp[:i + 1])이다. 풀이 n, k = map(int, input().split()) dp = [1] * (n + 1) k -= 1 while k: next_dp = [1] * (n + 1) for i in range(1, n + 1): next_dp[i] = sum(dp[:i + 1]) dp = next_dp[:] k -= 1 print(dp[-1] % 1000000000)