https://www.acmicpc.net/problem/2225
2225번: 합분해
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
MOD = 1000000000
n, k = map(int, input().split())
d = [[0] * (n + 1) for _ in range(k + 1)]
d[0][0] = 1
for i in range(1, k + 1):
for j in range(0, n + 1):
for l in range(0, j + 1):
d[i][j] += d[i - 1][j - l]
d[i][j] %= MOD
print(d[k][n])x + x + x + ... + L = N
일 때, L 이전까지의 수열들
합 = N - L개
개수 = K - 1개
이므로, D[K][N] = D[K - 1][N - L]이 된다.
'백준 알고리즘 (Baekjoon Algorithm)' 카테고리의 다른 글
| [파이썬] 백준 알고리즘 No.1309 동물원 (0) | 2022.01.15 |
|---|---|
| [파이썬] 백준 알고리즘 No.1149 RGB 거리 (0) | 2022.01.14 |
| [파이썬] 백준 알고리즘 No.14391 종이 조각 (0) | 2022.01.10 |
| [파이썬] 백준 알고리즘 No.10819 차이를 최대로 (0) | 2022.01.08 |
| [파이썬] 백준 알고리즘 No.16953 A -> B (0) | 2022.01.07 |