백준 11444번, 피보나치 수 6 (C, C++)

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

#include<iostream>
#include<vector>

using namespace std;
using matrix = vector<vector<long long>>;
matrix temp;

long long N;
matrix Do(matrix &A, matrix &B){
    matrix temp(2, vector<long long>(2)); // 초기화
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            for(int k = 0; k < 2; k++){
                temp[i][j] += A[i][k] * B[k][j];
            }
            temp[i][j] = temp[i][j] % 1000000007;
        }
    }
    return temp;
}

int main(){
    cin>>N;
    matrix A = {{1, 1},{1, 0}};
    matrix unit = {{1, 0}, {0, 1}};

    while(N>0){
        if(N % 2 == 1){
         unit = Do(unit, A);
        }
        A = Do(A, A);
        N = N/2;
    }
    cout<<unit[0][1];
}

해당 문제는 재귀로 해결 할 수 없습니다. 

O(2^n) 지수형이기 때문입니다.

캐시를 계속 저장하는 방식인 메모이제이션 또한 O(N)이기 메모리 제한 때문에 다른 방식으로 접근해야 할 것 입니다.

 

 

https://www.acmicpc.net/problem/10830 

10830번: 행렬 제곱

https://www.acmicpc.net/problem/2740

2740번: 행렬 곱셈

행렬의 거듭제곱과 단위 행렬을 이용하여 홀수인 경우와 짝수인 경우를 나눠줍니다.

행렬의 거듭제곱 방식은 시간복잡도 logN입니다. 따라서 시간을 최소화 해야하는 입장에서 적합합니다.

 

 

 

 

위의 식을 통해, n이 홀수인 경우를 단위 행렬을 이용해 처리해주도록 합니다.

N이 홀수인 경우,

단위 행렬과 A행렬을 서로 곱해, A를 만들어주고,

N이 N =/2 씩 줄어드는 만큼, 거듭제곱을 통해 2배씩 늘려줍니다.

어떠한 수든 결국엔 N이 1이라는 홀수가 나올 것인데,

제일 처음에 계산되었던 단위 행렬은 A행렬이 될 것이고 거듭제곱 되었던 A행렬과 다시 한 번 거듭 제곱을 하게 되면

결과적으로 단위 행렬에 거듭제곱의 값이 저장됩니다.    

 

N이 짝수인 경우, 맨 처음의 과정이 일어나지 않게 됩니다.