16195 1,2,3 더하기 9

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

#dp

16195번: 1, 2, 3 더하기 9

#16195 1,2,3 더하기 9
import sys
input=sys.stdin.readline
#스탠다드 인풋

t=int(input())
#테스트케이스 입력

order=[list(map(int,input().split())) for i in range(t)]
#order 입력

m=max(order)[0]
#max값 입력

dp=[[0 for i in range(j)] for j in range(m+1)]
#dp 입력

 

dp[1]=[1]
dp[2]=[1,1]
dp[3]=[1,2,1]
#초기값

for i in range(4,len(dp)):
    for j in range(1,i):
        if i-3>=j:
            dp[i][j]=(dp[i-1][j-1]+dp[i-2][j-1]+dp[i-3][j-1])%1000000009
        elif i-2>=j:
            dp[i][j]=(dp[i-1][j-1]+dp[i-2][j-1])%1000000009
        elif i-1>=j:
            dp[i][j]=(dp[i-1][j-1])%1000000009
#전에 본거랑 같음 ㅇㅇ 인덱스 0은 한자리 수 1은 두자리수 이런느낌

             
for c in order:
    n,m=c
    print(sum(dp[n][:m])%1000000009)

#돌려서 m번째 인덱스 전까지 다 더함

 

#더하기 시리즈 마지막 드디어 끝났다. dp에 대한 이해와 점화식에 대한 탐구를 지속적으로 한 결과라고 생각한다. 뒤쪽오니깐 이제 자동으로 t=int(input()) 이러고 있었네 ㅋㅋ. 아무튼 좋은 시리즈 였다. 위 문제는 사실 sum을 제외하면 이전 시리즈와 비슷해서 진짜 빠르게 풀었다. 규칙을 알고 이해해야 한다. 1의 자리숫자들은 1 2 3 을 넣으면 2의 자리 숫자로 바뀐다는 걸 알면 쉽게 이해가 가능하다.