[백준2749] / 피보나치 수 3 - 분할정복, 거듭제곱, DP (feat. 피사노 주기)

백준2749

 

푼 날짜 : 2024.10.01

푼 문제 : [2749] / 피보나치 수 3

사용한 언어 : python

알고리즘 : 분할정복, 거듭제곱, DP

 

 

푼 방법 : 

n의 범위를 잘 확인해야 한다. 값의 범위가 1000000000000000000 까지 가능하므로 메모리 초과가 날 가능성을 대비해야 한다!

다행히 출력 시에는 1000000으로 나눈 나머지를 출력한다.

 

요기서 뽀인트🌟🌟

 

피사노 주기(Pisano Period)에 대해 알고 계신가요?

 

 

전 이 문제를 풀면서 알게 되었답니다. ദ്ദി・ᴗ・)✧

 

 

피사노 주기란 ?

피보나치 수를 K로 나눈 나머지의 주기를 의미한다!

일정 주기가 반복되므로 해당 주기를 사용해 문제를 풀면 된다.

 

 

그래서 주기는 어떻게 구하는데 ?

mod = 10^k 일 때, k > 2 라면, 주기는 항상 15 × 10^(k-1) 이다.

 

라고 한다.

 

 

따라서 이 문제에서는 10^6(파이썬의 경우 10**6)으로 나누기 때문에 공식에 넣는다면 

mod = 10**6

반복 주기 p =15 * 10**5가 된다.

 

따라서 전체를 다 계산할 필요 없이, 반복 주기에 해당 하는 값을 구하여 해당 값을 찾아내면 된다!

 

 

코드 :

import sys

N = int(sys.stdin.readline())
dp = {}
dp[0] = 0
dp[1] = 1

mod = 10**6
p = mod//10*15  #위 공식 순서대로 작성하면 15*10**(6-1)로 작성 가능

for i in range(2, p):
    dp[i] = (dp[i-2]+dp[i-1])%mod

print(dp[N%p])

 

 

참고링크 :

https://www.acmicpc.net/blog/view/28

 

 

헤헤 몰랐던 걸 알게 되었다!!! 

오늘도 지식 += 1