[백준] 2749번 피보나치 수 3 (파이썬)

난이도 GOLD II

문제링크 : https://www.acmicpc.net/problem/2749

문제해결 아이디어

• N이 매우 크기 때문에 재귀로 접근하면 시간초과가 발생하고
• DP로 접근하면 메모리 초과가 발생한다.
• 피사노 주기를 활용해야 한다고 한다.

피사노 주기란?
피보나치 수를 K로 나눈 나머지는 항상 주기를 갖게 되는데 이를 피사노 주기라고 합니다.
주기의 길이가 P이면 N번째 피보나치 수를 M으로 나눈 나머지=(N% P) 번째 피보나치 수를 M을 나눈 나머지와 같은 공식을 얻을 수 있습니다.

나누려는 수가 10^k이고 이때의 k가 2보다 크다면 주기는 항상 15*10^(k-1)이 됩니다.

문제에 나오는 수로 대입을 해보면 M=10^6이기 때문에 주기는 15*10^5=1500000이고 이것을 이용하여 다음과 같이 해결할 수 있습니다.

소스코드

M=1000000
P=1500000

N = int(input())

def fibo3(n):
    a, b = 0, 1

    for _ in range(n):
        a, b = b%M, (a+b)%M
    return a

print(fibo3(N%P))