[Python] 백준 11444번: 피보나치 수 6

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

11444번: 피보나치 수 6

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
fibonacci = {0: 0, 1: 1, 2: 1}


def getFibonacci(n):
    if not fibonacci.get(n):
        if n % 2 == 1:
            fibonacci[n] = (getFibonacci((n+1)//2)**2 +
                            getFibonacci((n+1)//2-1)**2) % 1000000007
        else:
            fibonacci[n] = (getFibonacci(n+1) - getFibonacci(n-1)) % 1000000007

    return fibonacci[n]


if __name__ == '__main__':
    N = int(input())

    print(getFibonacci(N))

문제 분석에 3시간을 소비하고 코드 작성은 5분이 걸린 문제였다.

아무튼, 계속해서 문제를 고민하던 끝에 내린 결론은 다음과 같다.

 

n이 홀수일 때, F[n] = F[(n+1)/2]^2 + F[(n+1)/2-1]^2

 

가령, 아래와 같은 피보나치 수열이 있다고 하자.

여기서 위의 식을 이용하여, F[11]을 구하려면 아래와 같이 된다.

F[11] = F[6]^2 + F[5]^2 = 64 + 25 = 89

 

그럼, n이 짝수일 때는 어떻게 해야할까? 매우 쉽고 간단하다.

 

n이 짝수일 때, F[n] = F[n+1] - F[n-1]

 

이것을 통해 getFibonacci()라는 재귀 함수를 작성하면 된다.

또한, 이미 구했던 정보는 또다시 쓰일 수 있으므로 fibonacci라는 dictionary에 기록한다.