[BOJ2749] 피보나치 수 3

1. 문제

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

2749번: 피보나치 수 3

 

2. Note

풀이를 안 보고 풀긴 했지만 "단계별로 풀어보기"에서 행렬 곱셈을 사용하라는 힌트를 보지 못했으면 못 풀었을 것 같다.

피보나치 수열의 점화식은 선형성을 갖기 때문에 행렬의 곱으로 나타낼 수 있다.

 

+) 행렬 곱셈처럼 여러 인덱스 여러개 사용한다면 늘 인덱싱에 주의하자.

    실수 때문에 로직이 맞는데도 시간을 잡아먹는 경우가 잦다.

 

3. Reference

https://medium.com/@andrew.chamberlain/the-linear-algebra-view-of-the-fibonacci-sequence-4e81f78935a3

The Linear Algebra View of the Fibonacci Sequence