Algorithm/백준 알고리즘_Python
[알고리즘][Python] 백준(BOJ) 2688 줄어들지 않아_파이썬
알파이
2020. 11. 5. 08:29
2688 줄어들지 않아 www.acmicpc.net/problem/2688
2688번: 줄어들지 않아
첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (1 <= n <= 64)
www.acmicpc.net

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍
풀이
<내용>
- 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])
728x90
반응형