문제

풀이

점화식을 구해야 하는데
먼저 그림을 보면 각 삼각형의 변의 길이는 마주보고있는 두 삼각형인 바로 이전삼각형과 작은삼각형과의 변의 길이의 합으로 볼 수 있다

따라서 dp[i] = dp[i-1] + 작은 삼각형 변의 길이이고
작은삼각형은 i-5 번째 삼각형으로 볼 수 있다.

따라서 점화식은
dp[i] = dp[i-1] + dp[i-5]이다.

코드

# 점화식은 
# dp[i] = dp[i-1] + dp[i-5]이다.
#입력 테스트 케이스 T가 주어진다 각 테스트 케이스 마다의 dp[N]을 출력 해 준다.
import sys

dp = [0] * 101
dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 2
dp[5] = 2

for i in range(6, 101):
  dp[i] = dp[i-1] + dp[i-5]

T = int(input())

for k in range(T):
  N = int(sys.stdin.readline().rstrip())
  print(dp[N])