파이썬) 백준 알고리즘 | 11442번 : 홀수번째 피보나치 수의 합

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

11442번: 홀수번째 피보나치 수의 합

 

풀이

일단 f(n) - f(n-2) = f(n-1)이란 수식을 이용하면

$$ f(2) - f(0) = f(1) $$

$$ f(3) - f(1) = f(2) $$

$$ f(4) - f(2) = f(3) $$

$$ f(5) - f(3) = f(4) $$

$$ ... $$

$$ f(n) - f(n-2) = f(n-1) $$

위 식을 다 더하게 되면

$$ f(n+1) = f(1) + \sum_{k=1}^{n-1} f(k) $$

위 식을 유도할 수 있다.

 

그리고 

n = 2k, n= 2k-1일 때 0번째부터 n번째까지의 홀수번째 피보나치 수의 합은 같다.

$$ f(0) + f(1) + f(3) + f(5) + f(7) +  ... + f(2k-3) + f(2k-1) $$

$$ = f(1) + \sum_{k=1}^{2k-2}  f(k)$$

로 나타낼 수 있다.

따라서 위의 피보나치 합공식을 이용하면

n = 2k일 경우에는 f(n), n = 2k-1일 경우에는 f(n+1)을 사용할 수 있다.

$$ \because f(n=2k)=f(n=2k-1) $$

n = int(input())
dict = {}
def fibo(n):
    a = n // 3
    if n == 0:
        return 0
    elif n == 1 or n ==2:
        return 1
    else:
        if not n in dict.keys():
            if n > 100:
                dict[n] = (fibo(a) * fibo(n-a+1) + fibo(a-1) * fibo(n-a)) % 1000000007
            else:
                dict[n] = (fibo(n-1) + fibo(n-2)) % 1000000007
        return dict[n]
if n % 2 == 1:
    print(fibo(n+1))
else:
    print(fibo(n))