[Python/파이썬] 백준 11444번: 피보나치 수 6

문제

 

풀이

분할 정복을 이용한 거듭제곱이므로 피보나치 수를 제곱의 형태로 만들려고 노력했다.

 

노트에 끄적이다가 우연히 규칙 발견!!

 

n % 2 == 0 인 경우

Fn = F(n//2+1) ** 2 - F(n//2-1) ** 2

 

n%2 == 1 인 경우

Fn = F(n//2+1) ** 2 + F(n//2) ** 2

 

메모제이션도 활용해야 시간 초과가 나지 않는다.

코드

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 # 맨 처음에는 % 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(int(input())) % 1000000007)

 

마무리

수학과 관련된 문제라 바로 해답을 찾아볼까 고민했지만... 고민하다 보니 혼자 힘으로 풀 수 있었다!!