[백준/DP/11057] 오르막 수

이전 문제와 비슷해 접근하기가 다소 쉬웠다.

이미지 클릭시, 문제로 이동됩니닷 :)

이전 문제와 비교해서 주의 할 점은 시작 숫자로 0을 사용 할 수 있다는 것.

n=1 일 때, 오르막 수의 개수

0123456789

n=2 일 때, 오르막 수의 개수

0
    0123456789 // 10
1
    123456789 // 9
2
    23456789 // 8
3
    3456789 // 7
4
    456789 // 6
5
    56789 // 5
6
    6789 // 4
7
    789 // 3
8
    89 // 2
9
    9 // 1

대충 감이온다.
이 문제도 끝 숫자가 중요하다.
끝 숫자 다음 올 수 있는 수는 끝 숫자와 같거나 크거나 둘중 하나이다.

규칙은 표를 그려 구했다.

import sys
input = sys.stdin.readline
N = int(input())
# n=1 일 때 값으로 세팅
dp = [1]*10

# 2부터 시작
for i in range(2,N+1):
  # 1부터 9까지 반복
  for j in range(1,10):
    dp[j] = dp[j-1] + dp[j]

print(sum(dp)%10007)