boj11057 - 오르막 수 (python)

문제

https://www.acmicpc.net/problem/11057

코드

import sys
input = sys.stdin.readline
n = int(input())

# 수 0으로 시작 가능
dptable = [[0]*10 for _ in range(1001)] #행 = 자리수, 열 = 마지막 숫자
tmp = 0
sum_ = 0
for i in range(10):
    dptable[1][i] = 1

for i in range(2,n+1): # 자릿수
    for j in range(10): # 마지막 숫자
        dptable[i][j] = sum(dptable[i-1][j:])
    # print(dptable[i])

# print(dptable[n])
print(sum(dptable[n])%10007)

설명

이전 자리수의 각 수에서 마지막 숫자부터 9까지 더한 값이 현재 자리수의 각 수의 오르막 수의 갯수
즉 n=1일 때 나올수 있는 오르막 수는 0~9까지 10개
n=2일 때 나올 수 있는 오르막 수는 0(0~9), 1(1~9), ... ,9(9) 55개

이를 dptable로 표현하면
2차원 dptable 생성 - dptable[i][j] 일때 i = 자리수 , j = 숫자에서 1의 자리에 있는 수

dptable[i][j] = dptable[i-1][j~9]의 합