[BaekJoon/백준] 11444번 분할정복

피보나치를 구하는 방법 중, 행렬의 제곱을 이용한 방법이 있다.

 

메모이제이션을 사용한 피보나치는 O(N)의 시간복잡도를 갖는 반면

10830번에서 볼 수 있었듯, 행렬의 제곱은 분할정복을 사용해 O(logN)으로 해결할 수 있다.

https://www.acmicpc.net/blog/view/28

 

사실 10830번 코드를 거의 그대로 갖다가 썼다가, 계속 메모리 초과가 나와서 애를 먹었다..

이유는.. 10830번에서는 제곱수가 1부터지만 11444번에는 제곱수가 0부터 가능해서 예외가 있었던 것 ㅜ

#include <stdio.h>
#include <string.h>

long long arr[2][2];
long long original[2][2];
long long temp1[2][2];

int N = 2;
long long B;
int i, j, m;



// 재귀 속에서 정적 변수인 arr을 공용으로 사용하면서 업데이트해나감.
void pow_(long long k) {
    
    //10830번과 다르게 제곱수 B가 0일 때의 예외가 있다...
    if(k <= 1) { // k == 1에서 k <= 1로 교체 -> 피보나치 pow_(0)일 때가 있으므로..
        for(i = 0; i < N; i++) {
            for(j = 0; j < N; j++)
                arr[i][j] %= 1000000007LL;
        }
        return;
    }
    
    pow_(k / 2);
    
    // 재귀 결과 상태를 받아옴, int a = pow_(k / 2)라고 보면 됨.
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++)
            temp1[i][j] = arr[i][j];
    }
    
    // 비워주고
    memset(arr, 0, sizeof(arr));
    
    // 곱
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++) {
            for(m = 0; m < N; m++)
                arr[i][j] = (arr[i][j] + (temp1[i][m] * temp1[m][j])) % 1000000007LL;
        }
    }
    
    if(k % 2) {
        // temp1에 arr 결과값을 복사한 뒤
        for(i = 0; i < N; i++) {
            for(j = 0; j < N; j++)
                temp1[i][j] = arr[i][j];
        }
        // arr을 다시 비워주고
        memset(arr, 0, sizeof(arr));
        
        // 곱
        for(i = 0; i < N; i++) {
            for(j = 0; j < N; j++) {
                for(m = 0; m < N; m++)
                    arr[i][j] = (arr[i][j] + (temp1[i][m] * original[m][j])) % 1000000007LL;
            }
        }
        
    }
    
}

int main() {
    
    scanf("%lld", &B);
    
    
    arr[0][0] = original[0][0] = 1LL;
    arr[0][1] = original[0][1] = 1LL;
    arr[1][0] = original[1][0] = 1LL;
    arr[1][1] = original[1][1] = 0LL;
    
    pow_(B - 1); // 행렬곱에서 얻을 수 있는 최대 피보나치는 F(n+1) = 행렬 0,0 이므로 절약을 위해 이렇게 수행.
    
    //10830번과 다르게 제곱수 B가 0일 때의 예외가 있다...
    printf("%lld", (B==0)?0:arr[0][0]);
}

 

 

참고

www.acmicpc.net/blog/view/28

www.acmicpc.net/board/view/65909#comment-109920