BOJ 1003 피보나치 함수

https://www.acmicpc.net/problem/1003
시간 0.25초, 메모리 128MB
input :

• 테스트 케이스의 개수 T
• N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

output :

• 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력

---

피보나치 함수가 수행될 때 마다, 0과 1이 호출되는 횟수를 출력하는 것이다.

맨 처음엔 그냥 함수를 수행해서 기록하게 했음 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그러니까 당연히 시간이 초과 돼지.(돼지)

0과 1이 호출되는 횟수도 피보나치 함수의 점화식과 동일하게 증가한다. 그래서 이를 DP로 저장해놓고 출력하자.

import sys

data = [[0] * 41 for i in range(2)]

data[0][0] = 1
data[1][0] = 0

data[0][1] = 0
data[1][1] = 1

data[0][2] = 1
data[1][2] = 1

for i in range(3, 41):
    data[0][i] = data[0][i - 1] + data[0][i - 2]
    data[1][i] = data[1][i - 1] + data[1][i - 2]

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    print(data[0][n], data[1][n])