백준 11057 오르막 수

haruponea·2021년 4월 5일
0

BOJ

목록 보기
37/41

문제 링크https://www.acmicpc.net/problem/11057

풀이
dp[i][j]를 자릿수가 i이고 j로 끝나는 오르막 수라고 하면 쉽게 풀리는 dp문제였습니다. dp[i][j]는 자릿수가 i-1인 오르막 수에서 끝이 0 ~ j까지인 수를 더하면 됩니다. 점화식은 다음과 같습니다.
dp[i][j] = dp[i-1][0] +dp[i-1][1]+ ··· + dp[i-1][j-1] +dp[i-1][j]

python

import sys
input = sys.stdin.readline
n = int(input())
mod = 10007
dp = [[0]*10 for _ in range(n + 1)]
for i in range(10):
    dp[1][i] = 1
for i in range(2, n+1):
    for j in range(10):
        for k in range(0, j + 1):
            dp[i][j] += dp[i-1][k] % mod
print(sum(dp[n])%mod)

0개의 댓글