PS/백준
[Python] 9461번 파도반 수열, 그림 설명
s_omi
2024. 9. 13. 09:29
✏️ 문제

문제 파악
첨에 반복되는 게 있는 지 찾는데 안보였다..
고민하다가 문제에서 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])