반응형
문제
https://www.acmicpc.net/problem/11444
11444번: 피보나치 수 6
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
아래 풀이를 참고하여 풀었습니다.
행렬의 제곱을 이용해 n번째 피보나치 수를 구할 수 있습니다.
또한 행렬의 제곱은 분할 정복 기법을 사용해서 $O(logN)$으로 구할 수 있습니다.
https://www.acmicpc.net/blog/view/28
피보나치 수를 구하는 여러가지 방법
피보나치 수는 다음과 같이 정의되는 수열입니다. $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}$ 피보나치 수를 조금 써보면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 와 같습니다. 피보나치 수를 구하는 함수
www.acmicpc.net
소스코드
후기
행렬의 제곱을 이용해 n번째 피보나치 수를 구할 수 있다는 점이 신선했습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 1654 랜선 자르기 (Swift) (0) | 2023.04.13 |
|---|---|
| [BOJ] 백준 1920 수 찾기 (Swift) (0) | 2023.04.12 |
| [BOJ] 백준 10830 행렬 제곱 (Swift) (0) | 2023.04.12 |
| [BOJ] 백준 2740 행렬 곱셈 (Swift) (0) | 2023.04.12 |
| [BOJ] 백준 1629 곱셈 (Swift) (0) | 2023.04.11 |
