t=int(input()) for _ in range(t): n=int(input())
l=[-1,1,2,4]+[0 for x in range(n-3)] for i in range(4,len(l)):
l[i]=l[i-1]+l[i-2]+l[i-3] print(l[n])https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.www.acmicpc.net
일단 규칙을찾는다
(n)=n을 만드는 경우의 수
(1)= (1)
(2)=2 (1+1,2)
(3)=4 (1+1+1,1+2,2+1,3)
(4)=7 (1+1+1+1,1+1+2,1+2+1,2+2+1,2+2,1+3,3+1)
n이 4일때
n(1)에서 3을만들어야되므로 n(3), 4가지
n(2)에서 2를만들어야되므로 n(2) 2가지
n(3)에서 1을만들어야되므로 n(1)1가지
경우의수가 있다.
그러므로, n[i]=n[i-1]+n[i-2]+n[i-3] n[1]=1, n[2]=2, n[3]=3
의 점화식이 생긴다.
이를 배열에 넣고 dp돌리면 된다.