9095. 1,2,3 더하기 (규칙찾기)

n>=4부터 f(n)=f(n-1)+f(n-2)+f(n-3)이라는 규칙을 찾아내는 것이 관건

import sys
t=int(sys.stdin.readline())
dp=[0,1,2,4,0,0,0,0,0,0,0,0]
for i in range(t):
    n=int(sys.stdin.readline())
    for j in range(4,n+1):
        dp[j]=dp[j-1]+dp[j-2]+dp[j-3]
    print(dp[n])


#n=1일때: 1 ->1개
#n=2일때: 2 , 11 ->2개
#n=3일때: 111,12(2),3 ->4개
#n=4일때: 1111,112(3),22,31(2) ->7개
#n=5일때: 11111,1112(4),122(3),23(2),113(3) -> 13개
#n=6일때: 111111,11112(5),1122(6),222,3111(4),123(6),33 ->24개
#n=7일때=f(4)+f(5)+f(6)