[백준] 9461번(python 파이썬)

https://www.acmicpc.net/problem/9461

 

삼각형을 계속 이어나가면서 규칙을 찾는 문제이다.

 

내가 구한 점화식은

f(1) = 1

f(2) = 1

f(3) = 1

f(4) = f(3) + f(1)

f(5) = f(4)

f(6) = f(5) + f(1)

f(7) = f(6) + f(2)

f(8) = f(7) + f(3)

 

f(5)부터 규칙을 찾을 수 있었다..

 

t = int(input())

def padovan(n):
    dp = [-1] * n

    for i in range(n):
        if i < 3:
            dp[i] = 1
        elif i == 3:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            if i-5 < 0:
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1] + dp[i-5]
    return dp[n-1]


for _ in range(t):
    n = int(input())
    print(padovan(n))