[2일차] 시간복잡도 C - 2748: 피보나치 수 2

브론즈 Ⅰ

 

#include <iostream>
using namespace std;

void mul_matrix(long long F[2][2], long long M[2][2]);
void matrix_power(long long F[2][2], int n);

long long fib(int n) {
	long long F[2][2] = { { 1, 1 }, { 1, 0 } };

	if (n == 0) return 0;

	matrix_power(F, n - 1);
	return F[0][0];
}

void mul_matrix(long long F[2][2], long long M[2][2]) {
	long long x = F[0][0] * M[0][0] +
        F[0][1] * M[1][0];
	long long y = F[0][0] * M[0][1] +
        F[0][1] * M[1][1];
	long long z = F[1][0] * M[0][0] +
        F[1][1] * M[1][0];
	long long w = F[1][0] * M[0][1] +
        F[1][1] * M[1][1];

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

//기본 F 행렬의 n제곱 계산
void matrix_power(long long F[2][2], int n) {
	int i;
	long long M[2][2] = { { 1, 1 }, { 1, 0 } };

	for (i = 2; i <= n; i++) {
		mul_matrix(F, M);
	}
}

int main() {
	int N;
	scanf("%d", &N);
	printf("%lld", fib(N));
}

 

피보나치 수열의 점화식을 행렬 곱으로 나타낸 다음

행렬 곱을 계산하여 푸는 문제

 

이거 나중에 행렬곱 하나씩 곱하고있지 말고

그 거듭제곱 빨리 계산하는 방법

거듭제곱의 지수를 2진수로 바꾼다음에

dp로 계산해놓은 캐시에서 골라서 쓰는

그 방법으로 하면 o(logn)될 거 같은데

 

일단 위의 방법은 그냥 dp랑 똑같은 o(n)으로 알고있는데 아닐수도있음 나중에 확인