[Dynamic Programming] 파도반 수열

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

Description

아래와 같이 나선형으로 정삼각형을 그려나간다. (1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12) 

n번째 삼각형의 한 변의 길이를 구하라.

Idea

직접 삼각형을 그리다 보면 $ a_n = a_{n-1} + a_{n-5} $ 임을 쉽게 알 수 있다.

Code

a = [1, 1, 1, 2, 2]

for _ in range(95):
	# a_n = a_(n-1) + a_(n-5)
	a.append(a[-1] + a[-5])

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