9461번 : 파도반 수열 - Python

문제

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

풀이

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.
여기서 규칙을 찾아보면

P(i) = P(i-2) + P(i-3)

이다.

코드

from sys import stdin

input = stdin.readline

number = int(input())

for i in range(number):
    n = int(input())

    array = [1 for i in range(n)]

    for j in range(3,n):
        array[j] = array[j-2]+array[j-3]
    
    print(array[n-1])