[백준] 11057번: 오르막 수 (python)

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

---

dp 테이블을 2차원으로 구성해서 풀어가는 문제

규칙만 잘 생각하면 쉬운 문제였다.

---

n = int(input())

# 2차원 dp 테이블 생성
dp = [[0] * 10 for _ in range(1001)]

# 길이가 1인 경우 오르막 수
for i in range(10):
    dp[1][i] = 1
    
for i in range(2, n + 1):
    for j in range(10):
        cnt = 0
        # 마지막 자리가 현재 숫자보다 크거나 같은 경우를 모두 카운트
        for k in range(j, 10):
            cnt += dp[i - 1][k]
        dp[i][j] = cnt
        
print(sum(dp[n]) % 10007)