[백준] 2749 피보나치 수 3

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

피보나치 수열을 구하고 특정 수로 나누었을때 나머지의 값을 구하는 문제였습니다.

단순히 메모이제이션을 이용하여 풀이를 하려 하였으나, 입력 값이 최대 1,000,000,000,000,000,000 으로 매우 큰 수이므로 메모이제이션을 이용하더라도 시간 초과가 우려되었습니다.

 

학습 진행 중 피사노 주기 라는 내용을 학습하게 되어 피사노 주기를 이용하여 풀이했습니다.

2) 알고리즘

• 수학

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())

period = 15 * 10 ** 5               # 나누는 수가 10^k 일때, 나머지는 주기를 이루는데 주기는 항상 15 * 10^(k-1) 이다.
fibo = [0, 1]                       # 피보나치 수열

for i in range(2, period):                              # 피보나치 수열을 주기의 길이만큼만 구함
    fibo.append((fibo[i-2] + fibo[i-1]) % 1000000)      # 피보나치 수열 값을 1,000,000 나눈 나머지의 값을 저장

print(fibo[N%period])               # 주기의 몇번쨰에 해당하는지 구해서 값 반환

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

시간 초과로 인하여 피보나치 수열의 나머지값을 구하는 새로운 공식을 찾는데 어려움을 느꼈습니다.

(1) 참고 사이트

• 블로그
  피사노 주기에 대하여 학습하였습니다.

2) 새롭게 학습한 내용

피사노 주기 - 피보나치 수열을 어떠한 특정 값으로 나누는 경우, 일정 주기를 가지고 나머지 값이 반복 되는것을 말합니다.

특정수가 만약 10^k (k > 2) 인 경우, 주기는 15 * 10^(k-1) 의 길이를 갖게 됩니다.

---

🔗 문제 링크

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

2749번: 피보나치 수 3

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다