[Math] 9416번 - 파도반 수열(37일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline
#문제 개수
t = int(input())

for _ in range(t):
    #찾고자 하는 수열의 순서 입력
    n = int(input())
    #각 수열의 값을 저장하는 dp
    dp = [0 for _ in range(n+1)]
    #1~n까지 수열을 연산
    for i in range(1,n+1):
        #나선 하나를 생성하기 위해서는 삼각형 3개가 필요하므로
        #1~3번째까지는 수열의 값은 1
        if(i <= 3):
            dp[i] = 1
        #처음 생성된 나선을 기반으로 새로운 나선을 생성하기 위해서는 삼각형 2개가 필요하므로
        #4~5번째까지 수열의 값은 2
        elif(3 < i <= 5):
            dp[i] = 2
        #이후로는 나선을 생성하는데 삼각형 1개만 있으면 되므로
        #n-1번째 수열의 값과 n-5번째 수열의 값의 합을 취함
        else:
            dp[i] = dp[i-1] + dp[i-5]
    #목표 수열 값 출력
    print(dp[n])

#인사이트
#나선이 처음 생성되기 위해서는 삼각형 3개가 필요함
#이후 나선이 업데이트되는 것은 삼각형이 한 바퀴 회전할때마다임
#따라서 나선 형성에 요구되는 삼각형의 양이 3->2->1로 줄어들음
#완벽한 점화식을 짜려 하기보다 귀납적 접근이 효과적이었음