[백준 9461] 파도반 수열

문제

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

---

아이디어

P(N) = P(N-5) + P(N-1)로 나타낼 수 있다. P(N)의 값을 저장해놓고 사용하면 메모리를 절약할 수 있다.

이 때, P(5)까지는 직접 입력해주고 P(6)부터는 점화식으로 표현할 수 있다. 

---

Solution

t = int(input()) 

cache = [0 for _ in range(101)]

cache[1] = 1
cache[2] = 1
cache[3] = 1 
cache[4] = 2
cache[5] = 2
cache[6] = 3

for idx in range(7, 101) : 
    cache[idx] = cache[idx - 5] + cache[idx - 1]
    
for _ in range(t) :
    n = int(input())
    print(cache[n])