[python3] 1003번 피보나치 함수

그냥 평범하게 재귀적 용법을 사용하면 시간초과가 된다.

그래서 한번 나온 값들을 리스트에 저장하는 방식으로 풀었더니 성공했다!

N = int(input())

lst = [0] * 41
lst[0:1] = [0,1]

def fibonacci(n):
	if n <= 1:
		return lst[n]
	else:
		if lst[n] == 0:
			lst[n] = fibonacci(n-1) + fibonacci(n - 2)
		return lst[n]

for repeat in range(0,N):
	p = int(input())

	if p == 0:
		print("1 0")
	else:
		print("%d %d"%(fibonacci(p-1),fibonacci(p)))