[2688] 줄어들지 않아 In python

 

> dp문제

 

으윽 dp문제 너무 시러.. ㅠ..ㅠ

 

그래도 좀전에 풀었던 문제들이 dp였어서

그나마 내 기준에서는 쉽게 풀었다!!

 

---

n=1일때 -> 총 2가지
0, 1 

---

n=2일때 -> 총 55가지
00, ...  09 : 10
11, .... 19 : 9
22, .... 29 : 8
33, ... 39  : 7
44, ... 49 : 6
55, ... 59 : 5
66, ... 69 : 4
77, ... 79 : 3 
88, ... 89 : 2
99 : 1

 

1+2+...+10 = 55

---

n=3일때 -> 220가지
000 > 55가지
    00, ... 09
    11, ... 19
    ...
100 > 45가지
    11, ... 19
    22, ... 29
    33, ... 39
200 > 45-9=36가지
300 > 36-8=28가지
400 > 28-7=21가지
500 > 21-6=15가지
600 > 15-5=10가지
700 > 10-4=6가지
800 > 6-3=3가지
900 > 3-2=1가지
    

1+3+6+10+...55 = 220

 

---

n=4일때 -> 715가지
0000 > 220가지
    000 > 55
        00, ... 90
    100 > 45
        11, ... 19
        22, ... 29
1000 > 220-45=175
    100 > 45
    200 > 36
       

---

 

dp 리스트는 아래와 같이 움직임!

	0	1	2	3	4	5	6	7	8	9	10
n= 2	10	9	8	7	6	5	4	3	2	1	55
n= 3	55	45	36	28	21	15	10	6	3	1	220
n= 4	220	165	...								715
n= 5

 

 

 

 

for i in range(int(input())):
    n = int(input())
    dp = [[0 for _ in range(11)] for _ in range(n+1)]
    dp[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10]
    dp[1] = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 55]
    if n == 1:
        print("10")
        continue
    elif n == 2:
        print("55")
        continue
    for i in range(2, n+1):
        for j in range(11):
            if j == 0:
                dp[i][0] = dp[i - 1][10]
            elif j == 10:
                dp[i][j] = sum(dp[i])
            else:
                dp[i][j] = dp[i][j - 1] - dp[i - 1][j - 1]
    print(dp[n-1][10])