2749 피보나치 수 3 / 11444 피보나치 수 6

f(n) = f(a)×f(b) + f(a-1)×f(b-1) (a+b = n+1)
라는 법칙을 발견하였고
n을 절반씩 쪼개 a, b에 할당하는 식으로 재귀로 풀었다.

def f(n):
    if n in fibo:
        return fibo[n]
    elif n % 2 == 1:
        a = (n+1) // 2
        b = (n+1) // 2 - 1
        ret = (f(a)**2 + f(b)**2) % 1_000_000_007
        fibo[n] = ret
        return ret
    elif n % 2 == 0:
        a = n//2 + 1
        b = n//2
        c = n//2 - 1
        ret = (f(a)*f(b) + f(b)*f(c)) % 1_000_000_007
        fibo[n] = ret
        return ret
    
N = int(input())
fibo = {0:0, 1:1, 2:1}
print(f(N))

이렇게 제출해서 맞은 뒤 다들 행렬곱으로 풀었다는 사실을 알았다. 공부하러 갑니다.