[백준] 11444번 : 피보나치 수 6

문제

 

---

풀이

 

피보나치 수를 행렬의 곱셈을 이용해 푸는 문제이다.

솔직히 뭔 말인지 몰랐다. 행렬을 배운적 없으니...그래서 검색을 해보니까 피보나치 수의 점화식을 행렬로 표현할 수 있다는 글을 봤다.

 

과정은 잘 모르겠고 결과만 놓고보면 이렇다고 한다. 선형대수학이라도 배워둘 걸 그럤다.

물론 배웠어도 도움이 되진 않았을 것 같다만...

 

아무튼 이렇게 정리가 됐으니 이 문제는

myunji.tistory.com/258?category=1154147

[백준] 10830번 : 행렬 제곱

이 문제와 아주 유사해지는 것이다.

---

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<long long>> matrix;
const long long DIVISOR = 1000000007;
matrix init({
                    vector<long long>({1, 1}), //Fn-1, Fn
                    vector<long long>({1, 0})  //Fn, Fn-1
            });
matrix result;

matrix multiplyMatrix(int N, matrix A, matrix B) {
    matrix res(N, vector<long long>(N));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++)
                res[i][j] += (A[i][k] * B[k][j]);
            res[i][j] %= DIVISOR;
        }
    }
    return res;
}

matrix divide(long long n) {
    matrix tmp;

    if (n == 1) //더이상 나눌 수 없음
        return init;
    else {
        if (n % 2 == 0) { //짝수 거듭제곱일 때
            tmp = divide(n / 2);
            return multiplyMatrix(2, tmp, tmp);
        } else //홀수 거듭제곱일 때
            return multiplyMatrix(2, init, divide(n - 1));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;

    cin >> n;

    result = divide(n);
    cout << result[0][1] % DIVISOR << '\n';
}

전체 소스코드다.

10830번의 코드와 달라진 부분은 int형 2차원 벡터가 long long형이 된 것과 init 2차원 벡터의 존재?말곤 없다.