[알고리즘][Python] 백준(BOJ) 2688 줄어들지 않아_파이썬

 

2688 줄어들지 않아    www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이

<내용>

• 1인 경우 0 - 9 (10개)
• 2인 경우 00-09(10개), 11-19(9개), ..., 99(1개) : 10 + 9 + ... + 1 (55개)
  • 0으로 끝나는 건 1개
  • 1로 끝나는 건 2개
  • 2로 끝나는 건 3개
  • ...
  • 9로 끝나는 건 10개

 

 

<코드>

import sys
input = sys.stdin.readline

t = int(input())
n = [int(input()) for _ in range(t)]
m = max(n)

res = [0, 10]
dp = [1] * 10
for i in range(2, m+1):
    cnt = 0
    new_dp = [0] * 10
    for j in range(10):
        cnt += dp[j]*(10-j)
        for k in range(j, 10):
            new_dp[k] += dp[j]
    res.append(cnt)
    dp = new_dp
    
for i in n:
    print(res[i])