[BOJ] 1003. 파보나치 함수(python)

📌문제

💪아이디어

1. 0이나 1 방문 수 세기
   n-2, n-1에 해당하는 수가 0,1에 방문한 횟수를 더하면 n이 0,1에 방문한 횟수와 같다.
   

🥂코드

import sys
input = sys.stdin.readline

def cnt(cur,inx,one,zero):
    one[cur]+=one[inx]
    zero[cur]+=zero[inx]

T= int(input())
nums=[]
for _ in range(T):
    nums.append(int(input()))

max_val = max(nums)

one, zero = [0]*(max_val+1),[0]*(max_val+1)
if max_val==0:
    one.append(1)
    zero.append(0)
else: 
    one[1]=1
zero[0]=1

for inx in range(2,max_val+1):
    cnt(inx,inx-1,one,zero)
    cnt(inx,inx-2,one,zero)

for n in nums:
    print(zero[n],one[n])