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

주어진 삼각형 그림을 보면, 작은 삼각형의 합으로 다음 삼각형이 채워진다.

-> DP

 

주어진 그림을 그려보며 생각해보면, 점화식을 어렵지 않게 찾을 수 있다.

N	1	2	3	4	5	6	7	8
P(N)	1	1	1	2	2	3	4	5

P(8) = P(7) + P(3)

P(7) = P(6) + P(2)

P(6) = P(5) + P(1

-> P(N) = P(N-1) + P(N-5)이다.

 

풀이

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

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

t = int(input()) # 테스트 케이스 개수
for _ in range(t):
    n = int(input())
    print(dp[n])