백준 1003 피보나치 함수

과정

• 재귀로 피보나치를 구하는 코드가 있어서 그대로 실행했더니 시간초과가 나온다.
• 동적 프로그래밍을 연습한다.
• 40까지 모든 피보나치 연산을 한다. 각 과정의 연산값은 리스트에 저장하고, 다음 연산에서 사용한다.
• 0, 1을 호출하는 횟수이므로 초기화를 주의해서 한다.

  import sys
  input = sys.stdin.readline
  tc = int(input())

dp_0 = [0] 41
dp_1 = [0] 41
dp_0[0] = 1
dp_1[1] = 1

for i in range(2, 41):
dp_0[i] = dp_0[i-1] + dp_0[i-2]
dp_1[i] = dp_1[i-1] + dp_1[i-2]

for _ in range(tc):
N = int(input())
print(dp_0[N], dp_1[N])