[알고리즘 문제풀이] 피보나치 수 6

문제 제목 : 피보나치 수 6

문제 난이도 : 중

문제 유형 : 동적 프로그래밍, 분할 정복, 수학

https://www.acmicpc.net/problem/11444
시간 제한 : 1초
메모리 제한 : 256MB

문제풀이 아이디어

< 소스코드 >

n = int(input())
# list -> dict (인덱스를 알고 있으면 바로 해당하는 데이터로 접근하기 때문에 메모리 절약)
dp = dict()

def fibo(n):
      if dp.get(n) != None:
            return dp[n]
      if n == 0:
            return 0
      if n == 1 or n == 2:
            return 1
      if n % 2 == 0: # 짝수
            dp[n // 2 + 1] = fibo(n // 2 + 1) % 1000000007
            dp[n // 2 - 1] = fibo(n // 2 - 1) % 1000000007
            return dp[n // 2 + 1] ** 2 - dp[n // 2 - 1] ** 2
      else: # 홀수
            dp[n // 2 + 1] = fibo(n // 2 + 1) % 1000000007
            dp[n // 2] = fibo(n // 2) % 1000000007
            return dp[n // 2 + 1] ** 2 + dp[n // 2] ** 2

print(fibo(n) % 1000000007)

# 메모리 초과(실패) -> list를 사용했기 때문에 모든 메모리를 다 쓴다.
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 1

def fibo(n):
    if n == 0:
        return dp[0]
    if n == 1 or n == 2:
        return dp[1]
    if n % 2 == 0:
        dp[n//2 + 1] = fibo(n//2 + 1) % 1000000007
        dp[n//2 - 1] = fibo(n//2 - 1) % 1000000007
        return dp[n // 2 + 1] ** 2 - dp[n // 2 - 1] ** 2
    else: # 홀수
        dp[n // 2 + 1] = fibo(n // 2 + 1) % 1000000007
        dp[n // 2] = fibo(n // 2) % 1000000007
        return dp[n // 2 + 1] ** 2 + dp[n // 2] ** 2

print(fibo(n) % 1000000007)