[Baekjoon] 1003 - 피보나치 함수

🔗 Problem Link

1003번: 피보나치 함수

---

❔Thinking

• 피보나치 함수에서, 0과 1이 출력되는 횟수를 각각 출력한다.

---

💻Solution

import sys
T = int(sys.stdin.readline().rstrip())
zero_cnt = [1, 0]
one_cnt = [0, 1]
for i in range(2, 41):
    zero_cnt += [zero_cnt[i-1] + zero_cnt[i-2]]
    one_cnt += [one_cnt[i-1] + one_cnt[i-2]]

for _ in range(T):
    num = int(sys.stdin.readline().rstrip())
    print(zero_cnt[num], one_cnt[num])

---

🗝️keypoint

1. 재귀를 통해 피보나치 함수를 구현하여 0과 1의 출력을 구할 경우, 시간초과이다.
2. 피보나치 수열을 구하는 방법과 마찬가지로, 0과 1을 반환하는 횟수도 DP로 구할 수 있다.