백준 2749 - 피보나치 수3

123456789101112131415161718import sys n = int(sys.stdin.readline())m = 10 ** 6p = 15 * (10 ** 5)fibo = [0,1] if n < 2: print(fibo[n]) exit() for i in range(2,p): fibo.append((fibo[i-1]+fibo[i-2])%m) if i == n: print(fibo[n%p]) exit() print(fibo[n%p])cs 피보나치 수를 나눌 때 나머지는 항상 주기를 갖으며 이를 피사노 주기라 한다.주기의 길이를 p라고 하고 나누는 수를 m(= 10^k, (k>2))라 할 때, p는 항상 15 * 10^(k-1)을 성립한다.문제의 출력에서 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력하라 하였기에 m은 10^6이 되고 p는 15 * (10^5)가 된다.이를 활용해 문제를 해결하였다....

원문링크 : 백준 2749 - 피보나치 수3