[백준] 2688번:줄어들지 않아 (python 파이썬)

문제

www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

 

풀이

n == 3 일 경우까지 해 본다면,

규칙이 보인다 !

richard25.tistory.com/46

[Seop's의 코드풀이] 백준 2688 줄어들지 않아 - Python

이 설명을 참고하여 풀었다.

dp 배열을 dp[자릿수가 n일 때][0으로 시작할 때 부터 ~ 9로 시작할 때 까지의 경우의 수] 이런 식으로 설정해놓고,

dp[i][10]에는 dp[i]에 해당하는 합계를 저장해주었다.

소스코드

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    dp = [[0]*(11) for _ in range(n+1)]
    dp[1] = [1,1,1,1,1,1,1,1,1,1,10]
    if n == 1:
        print('10')
        continue
    for i in range(2, n+1):
        for j in range(11):
            if j == 10:
                dp[i][10] = sum(dp[i])
            elif j == 0:
                dp[i][0] = dp[i-1][10]
            else:
                dp[i][j] = dp[i][j-1] - dp[i-1][j-1]
    print(dp[n][10])