백준9461(파이썬) - 파도반 수열

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

9461번: 파도반 수열

• 이 문제는 기본적인 DP문제였다.
• 규칙을 찾아서 바텀업(Bottom-up) 방식으로 구현하는 문제였고, 규칙은 예시에서 주어진 수를 쭉 나열해보면 알 수있었다. i번째 삼각형 변의 길이는 i-1번째 삼각형 변의 길이와 i-5번째 삼각형 변의 길이를 더한 값임을 알 수 있었다.
• 여기서 1,2,3번째까지는 1로 똑같고 그 다음부터 값이 변한다.
• 나는 5번째까지는 값을 입력해주었고, 그 for문을 돌릴 때 range(4,n)으로 구현했는데 이 부분은 크게 상관없다.

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    dp = [0] * (100000)

    dp[0] = 1
    dp[1] = 1
    dp[2] = 1
    dp[3] = 2
    dp[4] = 2
    if n < 4:
        print(dp[n-1])
    else:
        for i in range(4,n):
            dp[i] = dp[i-1] + dp[i-5]
        print(max(dp))