https://www.acmicpc.net/problem/11057
λ©λͺ¨λ¦¬ : 123172 KB
μκ° : 120 ms
N = int(input())
dp = [[0 for _ in range(19)] for _ in range(1009)]
dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(2, N+1):
for j in range(10):
if j == 0:
dp[i][j] = sum(dp[i-1])
else:
dp[i][j] = dp[i][j-1] - dp[i-1][j-1]
print(sum(dp[N])%10007)
DP[][] λ°°μ΄μ 2μ°¨μμΌλ‘ μ μΈ
DP[x][y] β x : μ λ ₯μΌλ‘ μ£Όμ΄μ§λ μ«μ ( = μ€λ₯΄λ§μμ κΈΈμ΄ )
y : κ°μ₯ ν° μ리μ μ«μ
< μμ >
000 β dp[3][0]
3367 β dp[4][3]
dp[1] λ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] μΌλ‘ μ΄κΈ°ν
μμ κ·Έλ¦Όμ μν΄, dp[k][0] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + ... + dp[k-1][9]
dp[k][1] = dp[k-1][1] + dp[k-1][2] + ... + dp[k-1][9]
dp[k][2] = dp[k-1][2] + ... + dp[k-1][9]
.
.
.
dp[k][9] = ... dp[k-1][9]
λΌλ κ·μΉμ μ°Ύμ μ μμΌλ―λ‘