9461 - 파도반 수열

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

9461번: 파도반 수열

 

- Dynamic Programming

 

import sys
input = sys.stdin.readline

t = int(input())
a = list()
for _ in range(t):
    a.append(int(input()))

n = max(a)

dp = [1] * (n+3)
for i in range(4, n+1):
    dp[i] = dp[i-2] + dp[i-3]

for i in a:
    print(dp[i])

 

문제 보고 나열된 숫자 (1,1,1,2,2,3,4,5,7,9) 를 보고 규칙을 바로 찾아버렸다 ㅎㅎ..

dp[i] = dp[i-2] + dp[i-3] 이어서 바로 코드 작성 들어갓다

 

테스트 케이스로 여러 개 받는 문제라 가장 큰 값으로 dp 리스트를 채워서

나중에 한 번에 접근하는 방식으로 코드를 짰다

 

쉬운 디피 문제인듯!