피보나치 함수 [백준 1003](파이썬)

문제

---

피보나치 함수 백준 1003
https://www.acmicpc.net/problem/1003

풀이

---

시간 기준이 널널하지 않기 때문에 메모라이징과 조금의 규칙을 발견하여 다이나믹 프로그래밍을 사용하기로 했다. 규칙을 찾으려고 보니 0의 호출 개수는 1의 호출 가장 마지막 개수 1의 호출 개수는 이전 0의 개수와 이전 1의 호출 개수를 더한 규칙이 있었다

코드

---

t = int(input())
for _ in range(t):
    cnt_0 = [1, 0]
    cnt_1 = [0, 1]
    n = int(input())
    if n > 1:
        for i in range(n - 1):
            cnt_0.append(cnt_1[-1])
            cnt_1.append(cnt_0[-2] + cnt_1[-1])
    print(cnt_0[n], cnt_1[n])