문제 링크: https://www.acmicpc.net/problem/1003

풀이

피보나치 함수로 일일히 호출해서 세면 시간초과일 것 같아서 시도해보지 않음
값이 아닌 함수 호출 횟수를 dp로 만들면 되지 않을까 해서 작성해봤는데 통과했다.

점화식

• dp[0] = [1, 0] 0일 때 fibo(0) 호출횟수 1, fibo(1) 호출 횟수 0
• dp[1] = [0, 1] 0일 때 fibo(0) 호출횟수 0, fibo(1) 호출 횟수 1
• dp[n] = dp[n - 2]과 dp[n - 1]의 fibo(0) 호출횟수, fibo(1) 호출 횟수

코드

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    if n == 0:
        print(1, 0)
        continue
    dp = [[]] * (n + 1)
    dp[0] = [1, 0]
    dp[1] = [0, 1]
    for i in range(2, n + 1):
        dp[i] = [dp[i - 2][0] + dp[i - 1][0], dp[i - 2][1] + dp[i - 1][1]]
    print(*dp[-1])