[백준] 7677 Fibonacci

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

피보나치수를 구하는 문제였다.
다만 N의 최대가 1,000,000,000이라 예전에 dp로 풀었을 땐 시간초과가 났다.

이산수학에서 행렬을 배우고 다시 보니 풀 수 있을 것 같아서 다시 풀어봤다.

풀이

• 행렬의 거듭제곱을 이용해야한다.
• 다만, N번 곱한다면 시간복잡도가 O(N) 이기에 이문제는 풀 수 없다.
  분할정복을 이용한 거듭제곱 알고리즘을 사용해 O(logN)으로 풀 수 있다.

분할정복을 이용한 거듭제곱
N이 짝수 A^N = A^(N/2) * A^(N/2)
N이 홀수 A^N = A^((N-1)/2) * A^((N-1)/2) * A

2*2라 그냥 2차원배열로 만들까 생각도 했지만 이번기회에 벡터사용에 익숙해지면 좋을 것 같아 벡터를 사용했다.

우선 행렬 matrix를 vector를 이용해 선언해주고

typedef vector<vector<int>> matrix;

연산자 오버로딩으로 행렬의 곱연산을 정의해줬다. 3중 for문이라 구현이 어려운 것 같다.

matrix operator*(const matrix& a, const matrix& b)
{
    matrix res(size, vector<int>(size)); //크기를 지정하면 백터는 0으로 초기화됨

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            for (int k = 0; k < size; k++) //a의 행과 b의 열은 i,j,로 고정시키고 열과 행을 k로 바꾸면서 연산
            {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 10000; //10000으로 나눈 나머지.
        }
    }
    return res;
}

다음은 행렬과 정수를 받아 제곱을 해주는 함수이다.
반복문으로 구현할 수도 있지만 구현이 더 쉬운 재귀로 구현했다.

N이 10억이라 해도 재귀는 30번만 돌기때문에 메모리는 충분하다.

matrix power(matrix a, int b) //a^b
{
    if (b == 1) return a;
    if (b % 2 == 0)
    {
        matrix half = power(a, b / 2); 
        return half * half;
    }
    else
    {
        matrix half = power(a, (b - 1) / 2);
        return half * half * a;
    }
}

전체코드

#include <bits/stdc++.h>
#define size 2
using namespace std;

typedef vector<vector<int>> matrix;


matrix operator*(const matrix& a, const matrix& b)
{
    matrix res(size, vector<int>(size)); //크기를 지정해서 0으로 초기화됨

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            for (int k = 0; k < size; k++) //a의 행과 b의 열은 i,j,로 고정시키고 열과 행을 k로 바꾸면서 연산
            {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 10000; //10000으로 나눈 나머지.
        }
    }
    return res;
}

matrix power(matrix a, int b) //a^b
{
    if (b == 1) return a;
    if (b % 2 == 0)
    {
        matrix half = power(a, b / 2); 
        return half * half;
    }
    else
    {
        matrix half = power(a, (b - 1) / 2);
        return half * half * a;
    }
}

int main()
{
    int N; //0 <= N <= 1,000,000,000
    matrix res{ {1, 1}, 
                { 1,0 } };
    matrix original{ {1, 1},
                { 1,0 } };
    while (true)
    {
        cin >> N;
        if (N == -1) break;
        if (N == 0) { cout << 0 << '\n'; continue; }
        res = original;
        res = power(res, N);
        cout << res[0][1] << endl;
    }

    return 0;
}

행렬 곱연산은 size만 건드리면 되기에 다른 곳에도 써먹을 수 있을 것 같다.