728x90
풀이
다음과 같이 행렬을 이용해 피보나치 수를 구할 수 있다.
"백준 10830, 행렬 제곱" 코드를 이용해 완성했다.
소스코드
#include <stdio.h>
#define ll long long
const int MOD = 1e9 + 7;
ll X[2][2] = {0, 1, 1, 1};
void fibo(ll result[][2], ll f[][2]){
int temp[2][2] = {0,};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
temp[i][j] += (result[i][k]*f[k][j]) %MOD;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
result[i][j] = temp[i][j] %MOD;
}
int main(){
ll n, result[2][2] = {1, 0, 0, 1};
scanf("%lld", &n);
while (n){
if (n & 1) fibo(result, X);
fibo(X, X);
n >>= 1;
}
printf("%d ", result[1][0]);
}
출처 및 참고자료
11444번: 피보나치 수 6
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
피보나치 수를 구하는 여러가지 방법
피보나치 수는 다음과 같이 정의되는 수열입니다. $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
[백준 10830] 행렬 제곱 [C]
풀이 분할 정복을 이용한 거듭제곱 알고리즘으로 행렬의 제곱을 구현해주어야 시간 초과가 발생하지 않는다. 소스코드 #include int N; void square(int result[][5], int matrix[][5]){ int temp[5][5] = {0,};..
kyr-db.tistory.com
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 11778] 피보나치 수와 최대공약수 [C] (0) | 2021.08.21 |
---|---|
[백준 2086] 피보나치 수의 합 [C] (0) | 2021.08.21 |
[백준 10830] 행렬 제곱 [C] (0) | 2021.08.21 |
[백준 13172] Σ [C] (0) | 2021.08.20 |
[백준 16953] A → B [C/C++] (0) | 2021.08.20 |