피보나치 수 3 [백준 2749] - python

import sys 
input = sys.stdin.readline
target_num = 1e6

def find_routine() :
  routine = 1
  m1, m2 = 1, 2
  while True :
    if m1 == 1 and m2 == 1 :
      break
    
    m1, m2 = m2, (m1 + m2) % target_num
    routine += 1
  return routine

def BOJ2749():
  routine_length = find_routine()
  n = int(input())
  
  fibonacci = [0, 1, 1] + [0] * int(routine_length)
  for i in range(3, routine_length):
    fibonacci[i] = int((fibonacci[i-2] % target_num + fibonacci[i-1] % target_num) % target_num)

  print(fibonacci[n % routine_length])


BOJ2749()

 

접근 방법 :

   1. 피사노 주기를 이용할 것이다. 피보나치 수열에서 모듈러 연산에 대한 주기는 항상 존재한다. 이것이 피사노 주기다. 

   2. 모듈러 연산을 해주는 숫자는 1e6 이다. 이 숫자로 피사노 주기에 대한 총 길이를 구하고 값을 구해주자

   3. 코드에서는 불필요하게 두번 탐색이 이루어 졌지만 한번의 탐색으로 피사노 주기의 길이와 주기에 대한 값들을 알수 있을것 같다

 

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

2749번: 피보나치 수 3