[알고리즘] 피보나치 수 6

구현 방식

• 피보나치 수열을 아래의 사진과 같이 등비수열 행렬 점화식으로 나타낼 수 있다.

• 그리고 행렬의 거듭제곱은 분할 정복을 통해 구할 수 있다.

코드

• 최종 코드는 아래와 같다.

const int MATMAXSIZE = 3;
const long long MOD = 1000000007;

map<long long, Matrix> dict;

class Matrix
{

public:
	Matrix() { }
	Matrix(int r, int c) : row(r), column(c) { }

public:
	Matrix operator*(const Matrix& m)
	{
		Matrix result(row, m.column);
		for (int i = 0; i < result.row; i++)
		{
			for (int j = 0; j < result.column; j++)
			{
				// column == m.row
				for (int k = 0; k < column; k++)
				{
					result.mat[i][j] += (this->mat[i][k] % MOD) * (m.mat[k][j] % MOD);
					result.mat[i][j] %= MOD;
				}
				
			}
		}

		return result;
	}

	static void print(Matrix m)
	{
		for (int i = 0; i < m.row; i++)
		{
			for (int j = 0; j < m.column; j++)
			{
				cout << m.mat[i][j] << " ";
			}
			cout << "\n";
		}
	}

public:
	int row, column;
	long long mat[MATMAXSIZE][MATMAXSIZE] = {};
};


int  main()
{
	long long N;
	cin >> N;

	Matrix Mat(2,2);
	Mat.mat[0][0] = 1;
	Mat.mat[0][1] = 1;
	Mat.mat[1][0] = 1;
	Mat.mat[1][1] = 0;
	solution(Mat, N);

}


void solution(Matrix& r, long long N)
{

	if (N <= 1)
	{
		cout << N;
		return;
	}

	Matrix m0(1, 2);
	m0.mat[0][0] = 1;
	m0.mat[0][1] = 0;


	dict[1] = r;
	Matrix rn = calcExponent(N - 1);
	Matrix result = rn * m0;
	cout << rn.mat[0][0];

}

Matrix calcExponent(long long expo)
{
	if (dict.find(expo) != dict.end())
		return dict[expo];
	// 홀 수
	if (expo % 2 == 1)
	{
		dict[expo] = calcExponent(expo / 2) * calcExponent(expo / 2) * calcExponent(1);
		return dict[expo];
	}
	// 짝 수
	else
	{
		dict[expo] = calcExponent(expo / 2) * calcExponent(expo / 2);
		return dict[expo];
	}
}