BOJ - 9461

백준 문제 링크
파도반 수열

❓접근법

1. 문제에서 나타난 패턴으로 점화식을 찾으면,
   DP[i] = DP[i-3] + DP[i-2] ( i >= 4 일 때 ) 로 알 수 있다.
2. 이를 이용해 DP를 만들고, DP[N]을 출력하면 끝!

👌🏻코드

T = int(input())

for _ in range(T):
    
    N = int(input())
    
    if N in [1,2,3]:
        print(1)
        
    else:
        DP = [0] * (N+1)
        DP[1] = 1
        DP[2] = 1
        DP[3] = 1
        
        for i in range(4, N+1):
            DP[i] = DP[i-3] + DP[i-2]
            
        print(DP[N])