[백준 9461] 파도반 수열 - 파이썬

백준 9461 - 파도반 수열

---

* 풀이과정

1) 문제에 주어진 그림만으로도 규칙을 파악할 수 있다.

2) N>5 일 때, N번째 삼각형의 변의 길이는 N-1번째 삼각형의 변의 길이와 N-5번째 삼각형의 변의 길이의 합이다.

3) 즉, 다이나믹 프로그래밍을 이용하여 풀 수 있다. dp[i] = dp[i-1]+dp[i-5]

# dp 리스트 생성
dp = [0]*101
dp[1], dp[2], dp[3], dp[4], dp[5] = 1,1,1,2,2

# 점화식으로 dp 리스트 채우기
for i in range(6, 101):
    dp[i] = dp[i-1]+dp[i-5]

N = int(input())
for _ in range(N):
    idx = int(input())
    print(dp[idx])