[BOJ/python] 9461: 파도반 수열

문제

✔️ silver 3

문제 흐름

삼각형이 처음에 어떻게 시작하는지 감만 잡으면 수월하게 풀 수 있다.
삼각형은 다음과 같은 순서로 구성된다고 봤다.
노란색으로 칠해진 부분, 5개의 값은 앞의 값을 이용해 구할 수 없으므로 초기값으로 설정했다.
앞의 값을 이용해 같은 방법으로 다음 값을 구하는 방식을 사용함에서 DP임을 알 수 있다.

다만 이전에 다른 DP 문제들도 그랫듯이 모든 케이스에서 같은 수열(?)을 가지게 된다면 (피보나치 수열과 같이) 매번 새로 구할 필요 없이 이전에 구한 값이라면 바로 사용할 수 있도록 memo 리스트가 매 테스트케이스마다 초기화되지 않도록 했다.
입력값 T의 범위는 딱히 주어지지 않았지만 T가 매우 커질 경우 매번 n의 최대값인 100까지 구한다면 시간이 불필요하게 오래 걸릴 수 있다.

코드

# 파도반 수열
# dp

import sys
input = sys.stdin.readline

def dp (n: int):
    if n <= len(memo):
        return memo[n - 1]
    
    i = len(memo)
    while i != n:
        memo.append( memo[i - 1] + memo[i - 5] )
        i += 1
    # print(*memo)
    return memo[i - 1]

if __name__ == "__main__":
    t = int(input())
    memo = [1, 1, 1, 2, 2]

    for testcase in range(t):
        n = int(input())
        print( dp(n) )