1003번 (피보나치 함수)

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

첫째 줄에 N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

내코드

h={}

def fibo(n):
  global h

  if n==0:
    return n

  if n==1:
    return n

  if not n in h:
    h[n]=fibo(n-1)+fibo(n-2)

  return int(h[n])

def doit():
  num=int(input())
  i=0

  while i < num:
    newNum = int(input())
    print('%d %d'%(fibo(newNum-1),fibo(newNum)))
    i=i+1

doit()

풀이방법

한참해매다가 피보나치 수열의 값이 fibo(N)일때 0의 갯수는 fibo(N-1)와 같고 1의 갯수는 fibo(N)과 같다는것을 알았다. 하지만 백준은 나에게 런타임 에러를 줬다.

시간복잡도

O(N) 일것 같다. 40을 찾을때 O(41)? 왜냐면 hash를 썼으니까...?