문제

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

나의 코드

"""
1. 아이디어
핵심은 2차원 dp를 만들어 앞에 오는 숫자를 가지고 테이블을 구성하는 것?

2. 시간복잡도
O(90n) 정도?
"""

from sys import stdin
input = stdin.readline

n = int(input())
dp = [ [0] * 10 for _ in range(n+1) ] # dp[0]은 무시할 수 있게 n+1만큼 생성

# 1 자리수는 1로 초기화
for i in range(10):
    dp[1][i] = 1

# dp[N 자리 수][N자리 숫자일 때 해당 Index 앞에 올 수 있는 일의 자리 수]
# 2 자리수부터 시작
for i in range(2, n+1): # n 자리수
    for j in range(10): # index
        for k in range(j+1): # 뒷자리가 j일때 앞에올 수 있는 일의 자리 수
            dp[i][j] += dp[i-1][k]

print(sum(dp[n]) % 10007)
    

느낀점

앞에 풀었던 쉬운 계단 수 문제랑 비슷하다.
https://velog.io/@tyjk8997/%EB%B0%B1%EC%A4%80-DP-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8-%EC%88%98python
쉬운 계단 수 문제에서 조금만 더 생각하면 풀 수 있는 문제.