[백준] 2749번 피보나치 수 3 파이썬 코드

코드

# 1000000으로 나눈 값을 출력하라고 했으므로, 피사노 주기를 이용할 수 있다.

def pisano(num):
  ans = 0
  mod1, mod2 = 1,1
  while 1:
    if ans == num-1: # ans의 값이 num-1에 해당할 때 탈출
      break
    ans += 1 # 값 증가
    mod1, mod2 = mod2, (mod1+mod2)%1000000 # 다음 값으로 넘어간다.
  return mod1
k = int(input())
findindex = k%1500000 # 주기는 1500000이므로, 나머지를 찾아서 계산해주면 된다.
print(pisano(findindex))

아이디어

1. 피사노 주기는 피보나치 수열을 임의의 수로 나누었을 때 그 나머지가 주기를 띄는 것을 말한다.

2. 1에 따르면, 피보나치 수열을 1000000으로 나누었을 때 나머지는 피사노 주기를 가질 것이다.

3. 피사노 주기의 성질 중 하나는, 나누는 수가 10^n이면 주기는 15*10^(n-1)을 가진다.

4. 그렇다면 O(N)의 시간 복잡도를 이용하면 충분히 해결할 수 있다.

5. 입력 % 주기 == 몇 번째 수

6. 인덱스라고 생각하고 풀었기 때문에 -1을 해주면 해당 값을 찾을 수 있다.