https://www.acmicpc.net/problem/15988
15988번: 1, 2, 3 더하기 3각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.www.acmicpc.net
이전의 1,2,3더하기와 완전히 같은 문제다.
다른점이 있다면 dp의 길이가 1000001이라는 건데,
짜피 계산은 컴퓨터가하니 알 바 아니고
dp를 구할때마다 %m (문제조건)
만 해주면 쉽게 풀린다.
t=int(input())m=1000000009dp=[0 for _ in range(1000001)]
#dp[i]=i자리 수를 1,2,3의 합으로 나타내는 방법dp[1]=1dp[2]=2dp[3]=4for i in range(4,len(dp)):
dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%mfor _ in range(t):
print(dp[int(input())])