[백준] 9461번 문제 (파도반 수열) 파이썬(Python) 풀이

for _ in range(int(input())):
    n = int(input())

    dp = [0] * 101
    dp[1], dp[2], dp[3] = 1, 1, 1
    dp[4], dp[5] = 2, 2

    for i in range(6, n + 1):
        dp[i] = dp[i - 1] + dp[i - 5]

    print(dp[n])

가장 긴 변의 길이를 하나 씩 적어보면 5번째 긴 변부터 일정한 규칙으로 수열이 형성되는 것을 알 수 있다.

규칙은 바로 dp[index] = dp[index - 1] + dp[index - 5] 이며, 해당 식을 적용하면 정답을 구할 수 있다.