[파이썬, Python] 백준 9461: 파도반 수열

문제

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

9461번: 파도반 수열

코드

li = [0 for i in range(101)]
li[1],li[2],li[3] = 1, 1, 1

for i in range(4, 101):
    li[i] = li[i-2] + li[i-3]

t = int(input())
for _ in range(t):
    n = int(input())
    print(li[n])

설명

다이나믹 프로그래밍으로 규칙을 찾아서 구현을 하는 문제이다.

4번째 삼각형부터, n-2 번째와 n-3번째의 길이를 더한 길이가 한 변의 길이가 되므로 이를 구현해준다.