백준 2688 줄어들지 않아 / python

문제 : 2688

풀이 point

n = 1 -> 0 1 2 3 4 5 6 7 8 9
n = 2 -> 00 01 02 03 04 05 06 07 08 09
11 12 13 14 15 16 17 18 19
22 23 24 25 26 27 28 29
....
99

n = 3 -> 000 001 002 003 004 005 ... 009

이렇게 써보다 보면 규칙을 발견할 수 있다.

n = 2일때 0으로 시작하는 경우의 수는 10개, 1은 9개 ...
n = 3일때 0으로 시작하는 경우의 수는 (10+9+8+...1)개 1로 시작하는 경우의 수는 111부터 199까지 (9+8+7+...)

즉 n-1자리 일때 i로 시작하는 수~9로 시작하는 수를 모두 더한 값이 n자리 일때 i로 시작하는 경우의 수이다.

코드

#백준, 2688 줄어들지 않아

import sys
input = sys.stdin.readline

T = int(input().rstrip())
dp = [[0]*10 for _ in range(65)]

for i in range(10):
    dp[1][i] = 1

for i in range(2, 65):
    for j in range(10):
        for k in range(j, 10):
            dp[i][j] += dp[i-1][k]

for _ in range(T):
    ans = 0
    n = int(input())
    for i in range(10):
        ans += dp[n][i]
    print(ans)  

사족

나는 자꾸 규칙이 10+9+8+..+1 이런식으로 진행될거라 생각해서 너무 접근을 잘못했다...
ㅠㅠ
0이 하나씩 붙고 1이 하나씩 붙는거는 알았는데 자리수가 그전 자리수를 다 합친 값이라고는 생각 못했고, dp이차원 쓸 생각 못함 + 규칙은 비슷하게 알아냈는데 어케 구현할지를 몰랐음...