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

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

11057번: 오르막 수

규칙성을 찾으면 직관적으로 풀 수 있는 dp 문제였다 

봤더니 티어가 실버 1 이다 . 딱 그정도 수준인것 같긴 하다 ㅎㅎ..

말로 설명하기 어려워서 그림으로 그려보았다. 

1) 현재 N== 1, 즉 자리가 한자릿수일 때는 자기 자신이 오르막 수에 해당하므로 오르막 수가 1개이다. 

0, 1, 2, .. 9 이런 얘들이 한자릿수 오르막 수가 된다. dp[1][i] = 1값을 저장했다. 

 

2) 자리가 두자릿수일때부터 이전 자릿수에서의 오르막 수 개수를 재활용할 수 있다 

dp[i][j] += dp[i-1][k]

여기서 i 는 자릿수, j 는 시작하는 숫자, k 는 j 다음에 오는 숫자들이 된다. 

N = int(input())
dp = [[0] * 10 for _ in range(N+1)] # 0~9 와 자릿수
answer = 0
for i in range(10):
    dp[1][i] = 1 # 자기자신

if N == 1:
    print(sum(dp[N]))
    exit(0)

for i in range(2, N+1): # 자릿수 2, 3, ... N까지 연산 
    for j in range(0, 10): # 시작하는 숫자 0, 1, 2 ... 9 
        for k in range(j, 10): # j 다음에 올 수 있는 숫자 (dp 테이블에서  이전 자수 연산 값을 꺼내오기)
            dp[i][j] += dp[i-1][k]

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