[백준] 9461번 (python 파이썬)

t = int(input())

for _ in range(t):
    s = [0, 1, 1, 1]
    n = int(input())
    if n < 4:
        print(s[n])
    else:
        for i in range(4, n+1):
            s.append(s[i - 3] + s[i - 2])
        print(s[n])

1, 1, 1, 2, 2, 3, 4, 5, 7, 9

규칙을 보면

n +3 번째는 

n 과 n + 1 의 합이다

 

이것만 알면 쉽게 풀리는 문제이다