15992 1,2,3 더하기 7

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

15992번: 1, 2, 3 더하기 7

#15992 1,2,3 더하기 7

import sys
input=sys.stdin.readline
#스탠다드 인풋

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

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

dp=[[0 for j in range(i)] for i in range(max(order)[0]+1)]
#dp 리스트 작성

dp[1]=[1]
dp[2]=[1,1]
dp[3]=[1,2,1]

p=1000000009
#조건에 있는 숫자

'''
아이디어

dp[i][j]=dp[i-1][j-1]+dp[i-2][j-1]+dp[i-3][j-1]
이제 i-3에서는 옆에 3을 넣고 i-2면 옆에 2를 넣고 i-1이면 옆에 1 을 넣고
'''

for i in range(4,len(dp)):
    for j in range(1,len(dp[i])):
        if i-3>=j:
            dp[i][j]=dp[i-1][j-1]%p+dp[i-2][j-1]%p+dp[i-3][j-1]%p
        elif i-2>=j:
            dp[i][j]=dp[i-1][j-1]%p+dp[i-2][j-1]%p
        elif i-1>=j:
            dp[i][j]=dp[i-1][j-1]%p
        dp[i][j]%=p
for i in order:
    n,m=i
    print(dp[n][m-1]%p)

 

#처음에는 이렇게 했는데 생각을 한게 어짜피 조건 index 이상으로 넘어가지않으니깐 (i= i-1 i-2 i-3 이런식으로 사용되기 때문에) maximum을 정해서 거기까지만 돌아보자고 했었는데

 

 

#15992 1,2,3 더하기 7 정리

t=int(input())
#t 입력

order=[list(map(int,input().split())) for i in range(t)]
#순서 order 리스트

p=1000000009
#조건에 있음

maximum_item=max(i[1] for i in order)
maximum_index=max(order)[0]
#인덱스 값 뒤쪽의 리스트 안의 인덱스 값 의 최댓값을 각각 찾아준다.

dp=[[0 for i in range(j)] for j in range(maximum_index+1)]
#dp[i]는 i개의 원소를 가지고 주어진 값 중에 가장 높은 값까지만 dp가 필요하므로 maximum_item 이 최대값으로

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

for i in range(4,maximum_index+1):
    for j in range(1,i):
        if j>maximum_item-1:
            break
#끝까지 돌리는데 index 최대치를 넘기면 break

        if i-3>=j:
            dp[i][j]=dp[i-1][j-1]%p+dp[i-2][j-1]%p+dp[i-3][j-1]%p
        elif i-2>=j:
            dp[i][j]=dp[i-1][j-1]%p+dp[i-2][j-1]%p
        elif i-1>=j:
            dp[i][j]=dp[i-1][j-1]%p
#out of range 를 방지해야함

for i in order:
    n,m=i
    print(dp[n][m-1]%p)

#다 돌려

 

#위의 식에서 max(i[1] for i in order) 자체가 더 오래걸려서 시간조절에 실패했다 그냥 첫번째 코드 쓰는게 나을듯