피보나치 함수

https://www.acmicpc.net/problem/1003 (opens in a new tab)

내 풀이

첫 번째 풀이

시간 초과 오류가 발생한다. 아래 코드의 원리는 딱히 없다.
예를 들어, n = 3일 때, 피보나치 수열을 실행하면서 fibo(0)과 fibo(1)을 실행할 때마다 0, 1, 0 또는 1, 0, 1을 반환하고 fibo(n-1)과 fibo(n-2)를 실행할 때마다 fibo(n-1)의 cnt_0과 fibo(n-2)의 cnt_0을 더하고 fibo(n-1)의 cnt_1과 fibo(n-2)의 cnt_1을 더한다.
이런식으로 완전 탐색을 하는 함수이다.

test_case_count = int(input())
def fibo(n, cnt_0, cnt_1) :
  if n == 0 :
    return 0, 1, 0
  if n == 1 :
    return 1, 0, 1
  fibo1_data = fibo(n - 1, 0, 0)
  fibo2_data = fibo(n - 2, 0, 0)
  val = fibo1_data[0] + fibo2_data[0]
  cnt_0 = fibo1_data[1] + fibo2_data[1]
  cnt_1 = fibo1_data[2] + fibo2_data[2]
  return [val, cnt_0, cnt_1]
 
for _ in range(test_case_count) :
  n = int(input())
  v,cnt_0,cnt_1 = fibo(n, 0, 0)
  print(f"{cnt_0} {cnt_1}")

내 풀이 2

https://bio-info.tistory.com/122 (opens in a new tab) 👈 이 블로그에서 아이디어를 얻었는데 0이 호출된 횟수와 1이 호출된 횟수 역시 피보나치 수열을 이룬다는 아이디어에 착안해서 dp로 풀었다.

test_case_count = int(input())
 
cnt0_map = {}
cnt1_map = {}
cnt0_map[0] = 1
cnt0_map[1] = 0
cnt1_map[0] = 0
cnt1_map[1] = 1
 
def fibo(n) :
  cnt0 = 0
  cnt1 = 0
  if n not in cnt0_map :
    cnt0 = fibo(n - 1)[0] + fibo(n - 2)[0]
    cnt0_map[n] = cnt0
  else :
    cnt0 = cnt0_map[n]
  if n not in cnt1_map :
    cnt1 = fibo(n - 1)[1] + fibo(n - 2)[1]
    cnt1_map[n] = cnt1
  else :
    cnt1 = cnt1_map[n]
  return [cnt0, cnt1]
for _ in range(test_case_count) :
  n = int(input())
  cnt0, cnt1 = fibo(n)
  print(f"{cnt0} {cnt1}")

Number of Island ACM Craft