https://www.acmicpc.net/problem/1003

초고

def fibonacci(n,ans):
    if n == 0:
        ans[0]+=1
        return 0
    elif n==1:
        ans[1]+=1
        return 1
    else:
        return fibonacci(n-1,ans)+fibonacci(n-2,ans)

t=int(input())
for i in range(t):
    n = int(input())
    ans = [0]*2
    fibonacci(n,ans)
    print(str(ans[0])+" "+ str(ans[1]))

• 시간초과로 실패..
  문제에서 주는 곧이곧대로 재귀함수로 풀어서 그런가보다

• 시간 복잡도는 각 테스트 케이스에 대해 O(2^N).
  자신을 두 번 호출하기때문! 피보나치(n-1, ans) + 피보나치(n-2, ans) 이렇게.

2트

def fibonacci(n):
    if n == 0:
        return (1,0)
    if n == 1:
        return (0,1) # 리스트 안에 튜플로 0,1 카운트
    li = [(0,0)]*(n+1)
    li[0] = (1,0)
    li[1] = (0,1)
    for i in range(2,n+1):
        zero_cnt =li[i-1][0]+li[i-2][0]
        one_cnt = li[i-1][1]+li[i-2][1]
        li[i] = (zero_cnt,one_cnt)
    return li[n]

t=int(input())
for i in range(t):
    n = int(input())
    zero_cnt,one_cnt = fibonacci(n)
    print(str(zero_cnt)+" "+ str(one_cnt))

• 시간 복잡도는 각 테스트 케이스에 대해 O(N) for문을 2~n까지 돌기때문.

참고) 재귀 함수를 동적 프로그래밍으로 바꾸는 몇 가지 팁

https://velog.io/@mpfo0106/%EC%9E%AC%EA%B7%80-%ED%95%A8%EC%88%98%EB%A5%BC-%EB%8F%99%EC%A0%81-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%EC%9C%BC%EB%A1%9C-%EB%B0%94%EA%BE%B8%EB%8A%94-%EB%AA%87-%EA%B0%80%EC%A7%80-%ED%8C%81