BOJ - 1003

백준 문제 링크
피보나치 함수

❓접근법

1. 피보나치(0) 은 0과 1이 출력되는 횟수가 각각 1, 0
   피보나치(1) 은 0과 1이 출력되는 횟수가 각각 0, 1
   피보나치(2) 는 0과 1이 출력되는 횟수가 각각 0, 1
   피보나치(3) 은 0과 1이 출력되는 횟수가 각각 1, 2
   피보나치(4) 는 0과 1이 출력되는 횟수가 각각 2, 3
2. 즉 피보나치 2 ~ N+1까지는
   0과 1이 출력되는 횟수가 피보나치(N-1), 피보나치(N)임을 알 수 있다.
3. 이를 이용해서 출력하면 끝!

👌🏻코드

T = int(input())

for _ in range(T):
    
    N = int(input())
    
    
    if N == 0:
        print(1, 0)
    elif N == 1:
        print(0, 1)
    else:
        dp = [0] * (N+1)
        dp[1] = 1

        for i in range(2, N+1):
            dp[i] = dp[i-1] + dp[i-2]

        
        print(dp[N-1], dp[N])