백준알고리즘/c++/2749/피보나치 수3

피보나치를 구하는건 똑같다.
이번 문제의 차이는 숫자가 매우 크다는 점이다..

결국 출력은 나머지를 구해야한다.
처음의 아이디어는 피보나치를 행렬만들어서 집어넣어서 연산의 속도를 높이고 1000번째 숫자를 구하면 그 값을 나누어 출력하면 되지않을까 였다.

결과적으론 다른 값이 나왔다 이유에 대해선 공부가 조금 더 필요할 것같다.
풀이 법은  백준 홈페이지에 나와있는걸 보고 공부하는 식으로 했다
우선 이 문제는 피사노 주기라는 것을 이용해서 특정한 규칙을 찾아야한다.(피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 됩니다. 이를 피사노 주기(Pisano Period)라고 합니다.)

특정한 주기를 이용 하고 나머지는 비슷한 로직으로 풀어내면 된다.