[Python] 9461번 파도반 수열, 그림 설명

✏️ 문제

 

문제 파악

첨에 반복되는 게 있는 지 찾는데 안보였다..

고민하다가 문제에서 P(1)부터 P(10)까지 주는 이유가 있을 것 같아서 찾아보니 다음과 같은 반복이 보였다!

이를 토대로 점화식은 P(n) = P(n-1) + P(n-5) 이 나왔다.

 

 

알고리즘

• 다이나믹 프로그래밍 

 

 

코드

for _ in range(int(input())):
  p = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
  n = int(input())

  for i in range(len(p), n+1):
    p.append(p[i-1] + p[i-5])

  print(p[n])