[Python] 백준 9461번 파도반 수열(DP)

문제

풀이

예시를 곰곰히 보다 보면 인덱스 i번째의 값은 i-2 + i-3인 것을 알 수 있다.

따라서 이 규칙대로 저장을 하며 찾으면 된다.

t = int(input())

answer = []

for i in range(t):

    n = int(input())

    cache = [1 for _ in range(n)]

    for i in range(3, n):

        cache[i] = cache[i-2]+cache[i-3]

    answer.append(cache[n-1])

for i in answer:

    print(i)