BOJ - 2688

백준 문제 링크
줄어들지 않아

❓접근법

1. 숫자 0 ~ 9까지가 가질 수 있는 경우의 수를 DP로 만든다.
2. 초기값 DP = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
3. 만약 한 자리 숫자이면 ( N = 1 )
   DP = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
   1자리의 경우 0~9 까지 10개가 최대이므로 총 개수는 10개
4. 만약 두 자리 숫자이면 ( N = 2 )
   DP = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]로 변하게 된다.
   그 이유는 2자리의 경우
   00, 01, 02, ...~ ... 09로 0이 먼저 시작하는 자리는 10개
   11, 12, 13, ... ~ ... 19로 1이 먼저 시작하는 자리는 9개...
   이런 식으로 9가 먼저 시작하는 자리는 1개이다.
   그러므로 총 개수는 55개
5. 위 과정을 반복하여 인덱스를 늘려가며
   DP[i] = sum(DP[i:])로 바꿔준다.
6. 마지막으로 DP의 합을 출력하면 끝!

👌🏻코드

T = int(input())

for _ in range(T):
    
    N = int(input())
    
    DP = [1 for i in range(10)]
        
    for i in range(N-1):
        for j in range(10):
            DP[j] = sum(DP[j:])
                
    print(sum(DP))