[백준 9461 파도반 수열 문제] PYTHON

 

정삼각형의 변의 길이인 k는 1,1,1,2,2,3,4,5,7,9,~이다.

피보나치 수열의 느낌으로 5번째 index인 3을 보면 2번째 + 3번째 index인 1+2라는 것을 알 수 있다.

결국 i번째 index의 value는 i-2번째+i-3번째의 value이므로 아래와 같이 코드를 구현했다.

 

N = int(input())
inp=[]
for _ in range(N):
   inp.append(int(input()))

dp=[1,1,1,2,2,3,4,5,7]
for i in range(9,101):
    dp.append(dp[i-3]+dp[i-2])

for j in inp:
    print(dp[j-1])