[백준] 9461 파도반 수열 (파이썬 python)

 

 

문제 링크

 

 

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

9461번: 파도반 수열

 

 

문제

 

 

 

 

 

문제 풀이

 

 

문제에서 주어진 예제만으로 점화식이 쉽게 구해진 문제였다.

P[1], P[2], P[3]까지는 모두 1의 값을 가지고

n이 4부터 100까지의 값일 경우 P[n] = p[n - 3] + p[n - 2] 의 점화식을 가진다.

즉, 수열에서 2개 전, 3개 전 숫자끼리 더한 값이 현재 값이다.

 

 

p = [0 for i in range(101)]
p[1] = 1
p[2] = 1
p[3] = 1
for i in range(3, 101):
    p[i] = p[i - 3] + p[i - 2]
t = int(input())
for i in range(t):
    n = int(input())
    print(p[n])