[백준/BOJ] - 9461번 python 풀이 - DP

---

Key Point

1. 규칙은 다음과 같다.

idx 5부터 본인 idx 기준 -5 위치에 있는 값을 더해주어 다음 값을 정하는 로직.

2. n의 최댓값이 100이라 했으므로 그냥 100까지 dp 배열을 한번에 만들고

출력하라는 값을 출력해주면 된다.

 

---

import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * 100
dp[0] =1
dp[1] =1
dp[2] =1
dp[3] =2
dp[4] =2 
ex = []
for _ in range(n):
    ex.append(int(input().rstrip()))

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

for item in ex:
    print(dp[item-1])