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

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

11444번: 피보나치 수 6

이번 포스트에서는 백준 알고리즘 문제인 피보나치 수 6 을 포스트 하도록 하겠습니다.

 

해당 문제는 solved.ac 기준 골드 2에 위치한 문제입니다.

 

먼저 문제입니다.

N이 입력으로 주어졌을 때, 피보나치 수열에서 N번째 수를 1000000007로 나눈 나머지를 출력하는 문제입니다.

 

해당 문제는 기존에 알고 있던 피보나치 수열의 동적계획법 점화식인 dp[i] = dp[i - 1] + dp[i - 2] 로는 해결할 수 없습니다.

시간 제한이 1초로 주어지고 N이 최악의 경우 1억을 초과하게 됩니다. 따라서 O(N)인 점화식으로 해결할 수 없으므로, 분할정복 알고리즘으로 해결합니다.

 

먼저, 동적계획법 점화식은 선형 방정식으로, 행렬로 변환이 가능합니다.

F(N + 2) = 1 * F(N + 1) + 1 * F(N) = [1,1] * [F(N + 1), F(N)]

F(N + 1) = 1 * F(N + 1) + 0 * F(N) = [1,0] * [F(N + 1), F(N)]

 

따라서 위 식은 다음처럼 표현 가능합니다.

[[F(N + 2)], [F(N + 1)]] = [[1,1],[1,0]] * [[F(N + 1)],[F(N)]]

 

여기서  [[F(N + 2)], [F(N + 1)]] 이 부분을 M(N + 1),  [[1,1],[1,0]] 이 부분을 A,  [[F(N + 1)],[F(N)]] 이 부분을 M(N) 으로 치환했을 때  다음 식을 구할 수 있습니다.

 

M(0) = [[F(1)],[F(0)]] = [[1],[0]]   (피보나치 수열의 1번째 수와 0번째 수는 각각 1와 0으로 알고 있으므로. M(0)이 구해짐.)

M(1) = A * M(0)

M(2) = A * M(1) = A * (A * (M0)) = A^2 * M(0)

M(N) = A^N * M(0)

 

따라서, N번째 피보나치 수는 A 행렬의 N제곱과 M(0)의 행렬을 곱한 값으로 구할 수 있습니다.

 

EX) [[F(8+1)],[F(8)]] = [[1,1],[1,0]] ^ 8 * [[1],[0]]

                                 =  [[34, 21], [21, 13]] * [[1],[0]]

                                 = [[34],[21]]

                                  F(9) = 34, F(8) = 21

 

위 예시에서 알수있는 점으로, A^N 제곱 수행했을 때 나오는 행렬은 다음과 같은 형태로 일반화됩니다.

 

[[F(N+1), F(N)], [F(N), F(N-1)]]

 

따라서 행렬 A의 제곱식 만으로 N번째 피보나치 수를 구할 수 있습니다.

하지만 행렬의 제곱식은 O(N^3)으로 시간초과가 발생하기 때문에 분할정복 알고리즘을 적용시켜야합니다.

 

EX) M^11 = M^5 * M^5 * M^1

       M^5 = M^2 * M^2 * M^1

       M^2 = M^1 * M^1

즉 차수가 홀수일때 M^N = M^(N/2) * M^(N/2) * M^1의 형태로 계산가능해집니다.

 

짝수일 경우는 M^N = M^(N/2) * M^(N/2)의 형태로 계산가능해집니다.

 

위 방식으로 차수가 1이 될때 까지 분할한 후, 정복하게 되면 곱하는 횟수가 줄어들게 되므로, O(log n)의 시간복잡도로 최적화됩니다.

 

다음은 C++ 코드입니다.

 

#include <iostream>
 
using namespace std;
 
const long long mod = 1000000007;
 
void multiply(long long int a[2][2], long long int b[2][2], long long int res[2][2]) {
    for(int i = 0; i < 2; i++) {
        for(int k = 0; k < 2; k++) {
            long long int tmp = 0;
            for(int l = 0; l < 2; l++) {
                tmp += a[i][l] * b[l][k];
            }
            res[i][k] = tmp % mod;
        }
    }
}
 
void copyArr(long long int a[2][2], long long int b[2][2]) {
    for(int i = 0; i < 2; i++) {
        for(int k = 0; k < 2; k++) {
            b[i][k] = a[i][k];
        }
    }
}
 
void conq(long long int a[2][2], long long int tmp[2][2], long long int res[2][2], long long int n) {
    if(n == 1) {
        copyArr(a,res);
        return;
    }
    
    conq(a, tmp, res, n/2);
    copyArr(res, tmp);                    //위의 조건문에 의해 res는 a를 가짐. (점화식에서 a의 거듭행렬을 통해 피보나치수 구함.) 이 식에 도달하면, 분할이 끝남.
    multiply(tmp, tmp, res);            //tmp의 거듭행렬. 위의 copyArr()로 tmp는 a를 가짐.
    
    if(n % 2 == 1) {
        copyArr(res, tmp);
        multiply(tmp, a, res);
    }
    copyArr(res, tmp);
}
 
int main() {
    long long int n;
    cin >> n;
 
    long long int a[2][2] = {{1,1}, {1,0}}, tmp[2][2], res[2][2];
    fill(tmp[0]. tmp[0] + 4, 1);
 
    conq(a, tmp, res, n);
 
    cout << res[0][1];
    return 0;
}

다음은 Python 코드입니다.

 

mod = 1000000007
 
def multiply(a, b, res) :
    for i in range(2) :
        for k in range(2) :
            tmp = 0
            for l in range(2) :
                tmp += a[i][l] * b[l][k]
            res[i][k] = tmp % mod
 
def copyArr(a, b) :
    for i in range(2) :
        for k in range(2) :
            b[i][k] = a[i][k]
 
def conq(a, tmp, res, n) :
    if n == 1 :
        copyArr(a, res)
        return
    
    conq(a, tmp, res, n // 2)
    copyArr(res, tmp)
    multiply(tmp, tmp, res)
 
    if n % 2 == 1 :
        copyArr(res, tmp)
        multiply(tmp, a, res)
    copyArr(res, tmp)
 
n = int(input())
a = [[1,1], [1,0]]
tmp = [[1,1],[1,1]]
res = [[1,1],[1,1]]
 
conq(a, tmp, res, n)
 
print(res[0][1])

해당 문제는 O(N)의 시간복잡도를 가지는 피보나치 수열의 점화식을 행렬의 거듭제곱과 분할정복 알고리즘을 사용하여

O(log N) 으로 최적화 하여 해결해야 하는 문제로 난이도가 꽤 높은 문제라고 생각합니다.

 

다음 포스트에서 또 다른 백준 알고리즘 문제로 포스트 하도록 하겠습니다. 감사합니다.