백준 2749 <피보나치 수 3> Python

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

---

해당 문제는 '피사노 주기' 라는 개념을 알고 있다면 쉽게 풀 수 있습니다.

Pisano period - Wikipedia

피사노 주기는 피보나치 수열의 주기에 관한 내용입니다.

그 중 해당 문제에서는 n>2 일 때, 피보나치 수를 10^n 로 나눈 나머지는 15x10^(n-1) 의 주기를 따른다는 속성을 이용합니다.

---

import sys

input = sys.stdin.readline
      

def solution(n):
    ## 피사노 주기
    # 주기는 10^6 일 때 15 * (10^5)
    # n 주기로 나눠주기
    n %= 15*(pow(10, 5))
    # DP
    memo = [0, 1]
    # 순회
    for i in range(2, n+1):
        memo.append((memo[i-1] + memo[i-2])%1000000)
    
    print(memo[n])


# 입력
n = int(input().strip())

solution(n)