[Baekjoon] 백준 2749번 Python

백준 2749번

사전지식 : 피보나치 수열(피사노 주기(Pisano Period)), 동적프로그래밍(Dynamic Programming)

피보나치 수열

피사노 주기(Pisano Period)

• 피사노 주기란 피보나치 수열 $F_n$을 어떤 정수 $m$으로 나눴을 때 나머지가 주기적으로 반복되는 성질에서 나오는 최소 주기
  
  
• 정의와 성질:
  
• 계산 예시:
  
• 일반화:
  
• 요약 : 피사노 주기는 피보나치 수열 나머지의 반복 주기를 의미하며, 이는
  $m$의 값에 따라 달라짐
  

N = int(input())

m = 1000000
fi = [0, 1]
p = m//10 * 15 

for i in range(2,p):
    fi.append(fi[i-1] + fi[i-2])
    fi[i] %= m

print(fi[N % p])

코드설명

1. $N$값이 매우 크고, $10^k$로 나누는 문제기 때문에 ‘피사노 주기’를 사용해서 풀어야함
   
   
2. 피사노 주기: 피보나치 수를 $K$로 나눈 나머지는 항상 주기를 갖게된다는 원리.
   
   
3. 주기가 $P$일때, $N$번째 피보나치 수를 $M$으로 나눈 나머지와 $\frac{N}{P}$번째 피보나치 수를 $M$으로 나눈 나머지와 같다 +
   $M = 10^k$일때, $k > 2$라면, 주기는 항상 $15*10^{k-1}$임
   
   
4. m이 $10^6$임으로 $k = 6$ 즉, $P = 10^{6-1} * 15 = \frac{10^6}{10} * 15 = \frac{m}{10} * 15$로 표현 가능함
   
   
5. 피보나치 수의 0번째와 1번째는 0, 1이며 $N$번째$(N≥2)$는 피보나치 수열의 점화식으로 표현 가능함
   
   
6. 반복문으로 피보나치 수를 완성시켜 나가며 피사노 주기를 활용할 것이기 때문에 한 주기만 계산
   
   
7. 피보나치 수를 주기로 나눈 나머지값을 출력