[ 2688 ] [ DP ] 줄어들지 않아

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

2688번: 줄어들지 않아

 

---

풀이 과정

---

1. 맨 앞자리에 K가 들어오려면 이전 자리에는 K~9가 들어올 수 있다.
   1. 따라서 점화식을 구성하면 DP[i][K] = DP[i-1][K] + DP[i-1][K+1] + ... + DP[i-1][9]
   2. 해당 점화식을 이용하여 DP 테이블을 채워주면 된다. 단, 한자리일때는 자기 자신을 고를때밖에 없으므로 1로 설정하여 준다.
2. 이후 각각의 테스트 케이스에 입력받은 자리수에 맞추어서 DP 테이블에서의 합계를 구해서 출력시켜 준다.
   • 예를 들어, 자릿수 4를 입력받으면 DP[4]의 합계를 출력시켜 주면 된다.

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().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]

T = int(input())
for _ in range(T):
    C = int(input())
    print(sum(dp[C]))