[BaekJoon] 백준 9461번 : 파도반 수열

9461번 : 파도반 수열

이런 종류의 문제는 일단 어느정도 계산을 해서 수열을 만든 다음 계속 쳐다보면 규칙이 보인다..

그리고 수열의 처음부터 규칙을 찾기보다 중간 지점에서 부터 규칙을 찾으면 명확히 보인다.

점화식은 dp[i] = dp[i - 5] + dp[i - 1], i >= 5 이다.

따라서 dp 배열을 [1, 1, 1, 2, 2] 로 초기화를 시킨 뒤 dp[99] 까지 DP 를 이용하여 구하고 출력을 하면 된다.

아니면 dp[i] = dp[i - 3] + dp[i - 2], i >= 3 의 방법도 가능하다.

---

arr = [1, 1, 1, 2, 2]

for i in range(5, 100):
	arr.append(arr[i - 5] + arr[i - 1])

for _ in range(int(input())):
	print(arr[int(input()) - 1])