백준 11444 피보나치 6

피보나치 6 (백준 11444)

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

기존에 푸는 방식으로는 아무리 빨라도 O(n)이였기에
다른 방식을 고려해야 했지만,
고민해도 명확한 답이 없었기에 블로그를 보았다

기본적으로는 ‘행렬의 제곱’을 통한 증명을 통해 푸는 방법과
피보나치의 수에서 특정한 규칙을 찾아, 푸는 방법이 존재하였는데
DP를 통한 접근 방식이 더 깔끔했다 생각하였기에
해당 방식을 통해 풀었다

행렬 및 선형대수에 대한 공부가 더 필요하다고 느끼고 있다

[DP]https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-11444-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98-6-%EA%B3%A8%EB%93%9C3-%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5 [DQ]https://chaemi720.tistory.com/281

Code

import sys

DIVIDE_VALUE = 1000000007

inp = sys.stdin.readline
sys.setrecursionlimit(10**8)

# DP 방식으로 푸는 방식
# top-down
dp = dict()

# n이 짝수일 떄와 홀수일 때의
# 공식을 다르게 하여 구함

def fibo(n):
    if dp.get(n):
        return dp[n]
    if n == 0:
        return 0
    if n <= 2:
        return 1

    if n % 2 == 0:
        dp[n // 2 + 1] = fibo(n // 2 + 1) % DIVIDE_VALUE
        dp[n // 2 - 1] = fibo(n // 2 - 1) % DIVIDE_VALUE
        return dp[n // 2 + 1] ** 2 - dp[n // 2 - 1] ** 2

    dp[n // 2 + 1] = fibo(n // 2 + 1) % DIVIDE_VALUE
    dp[n // 2] = fibo(n // 2) % DIVIDE_VALUE
    return dp[n // 2 + 1] ** 2 + dp[n // 2] ** 2


n = int(inp().strip())

print(fibo(n) % DIVIDE_VALUE)

해결 아이디어

1. 함수의 입력값이 홀수라면, F(n) = F(n//2 + 1) ^ 2 - F(n//2- 1) ^ 2
2. 함수의 입력값이 짝수라면, F(n) = F(n//2 + 1) ^ 2 + F(n//2)^2
3. 다만 특정한 값으로 나눈 값으로 받아야 하기에 해당 요소들을 저장할 때,
   DIVIDE_VALUE로 나누어 저장