[Baekjoon,2749] 피보나치 수 3
이 문제를 해결하기 위한 방법이 두 가지 정도 있는데 하나는 피사노 주기를 이용하는 것이고, 다른 하나는 행렬을 이용하는 것이다. 여기서는 행렬을 이용한 방법만 소개하겠다.
행렬로 해결
수열을 행렬로 변환
피보나치의 수는 $ 1,1,2,3,5,8,13, \cdots $과 같이 증가한다. 이를 점화식으로 나타내면 아래와 같다.
$ F_0=1, \ \ F_1=1 \\
F_n=F_{n-1}+F_{n-2} \ \ (n=2,3,4 \cdots) $
선형대수학으로 피보나치 수열의 일반항을 구하는 방법으로 위 점화식을 다음과 같은 행렬로 변환할 수 있다.
$ \begin{bmatrix}
F_{n} \\
F_{n-1}
\end{bmatrix}
=
\begin{bmatrix}
F_{n-1} + F_{n-2} \\
F_{n-1} + 0 \times F_{n-2}
\end{bmatrix}
$
이는 행렬의 곱셈을 이용하여 아래와 같이 표현할 수 있다.
$ \begin{bmatrix}
F_{n} \\
F_{n-1}
\end{bmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{bmatrix}
F_{n-1} \\
F_{n-2}
\end{bmatrix}
$
여기서 $ x_{n} = \begin{bmatrix}
F_{n} \\
F_{n-1}
\end{bmatrix} , \
A= \begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} $ 라고 하자.
그러면 $ x_{n}=Ax_{n-1} $ 이므로 아래와 같은 접근이 가능하다.
$ x_{n}=Ax_{n-1}=A(Ax_{n-2})=A^2(Ax_{n-3}) \\
= \cdots = A^{n-1}x_1, \ \
x_1=\begin{pmatrix}
1 \\
1
\end{pmatrix} $
즉, $A^{n-1}$을 구하기만 하면 $n$번째 피보나치 수를 얻을 수 있다.
빠른 제곱
그런데 행렬 $A$를 제곱하기에는 주어진 입력이 너무 크다. 이를 해결하기 위해서는 분할하여 제곱하면 된다. 처음부터 하나씩 행렬을 곱하지 않고 둘로 쪼개어 제곱하는 방식이다. 이에 대한 자세한 설명은 백준: 행렬 제곱 풀이에서 볼 수 있다.
구현
#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<long long> > Mat;
const int MOD=1000000;
const int n=2;
// 행렬의 곱셈
Mat operator*(const Mat& a, const Mat& b)
{
Mat ret(n,vector<long long>(n,0));
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
{
for(int k=0;k<n;++k)
ret[i][j]+=a[i][k]*b[k][j];
ret[i][j]%=MOD;
}
return ret;
}
// 행렬의 거듭 제곱
Mat pow(const Mat& mat, long long p)
{
// 기저 사례: 항등 행렬 반환
if(p==0)
{
Mat temp(n,vector<long long>(n));
for(int i=0;i<n;++i)
temp[i][i]=1;
return temp;
}
if(p&1)
return mat*pow(mat,p-1);
Mat half=pow(mat,p/2);
return half*half;
}
int main()
{
long long p;
cin>>p;
if(p<2)
{
cout<<1<<endl;
return 0;
}
Mat mat(n,vector<long long>(n,0));
mat[0][0]=mat[0][1]=mat[1][0]=1;
Mat ret=pow(mat,p-1);
cout<<ret[0][0]<<endl;
return 0;
}
댓글남기기