백준 9416 파이썬(DP)

이 문제도 점화식을 구하면 쉽게 풀 수 있는 문제다

 

그림을 유심히 살펴보거나

혹은 결과들을 유심히 살펴보면 숫자들간에 규칙이 있는것을 발견할 수 있다.

(사실 다른 더 논리적이고 멋있는 해설이 있기야 하겠지만 나는 이렇게 풀었다...;;)

 

• 점화식

$$ a_n = a_{n-5} + a_{n-1} $$

 

• 코드

# 9461번 - 파도반 수열

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    dp = [0] * 101
    dp[1] = 1
    dp[2] = 1
    dp[3] = 1
    dp[4] = 2
    dp[5] = 2
    n = int(input())
    for i in range(6,n+1):
        dp[i] = dp[i-5] + dp[i-1]
    print(dp[n])