[BaekJoon] 2749번 - 피보나치 수 3 [Java][C++]

문제 링크

---

1. 문제 풀이

피보나치 수열에서 $n$ 번째 수를 구하는 문제로 $n$ 의 크기가 매우 크다. 피보나치 수를 구하는 점화식을 활용한 행렬 연산과 이진 거듭제곱 을 활용하면 해결할 수 있다.

$a_n = a_{n-2} + a_{n-1}$ 의 점화식을 갖는 피보나치 수열은 아래와 같은 행렬 연산으로 바꿀 수 있다.

\[\binom{a_n}{a_{n-1}} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \binom{a_{n-1}}{a_{n-2}} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^2 \binom{a_{n-2}}{a_{n-3}} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \binom{a_1}{a_0}\]

이렇게 변환하면 큰 수의 행렬 거듭제곱을 구하는 문제로 변형해서 해결할 수 있다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;

public class Main {

    static final int MOD = 1_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long N = Long.parseLong(br.readLine());
        if (N == 0) {
            System.out.println(0);
            return;
        }

        long[][] res = binPow(baseMatrix(), N - 1);
        System.out.println(res[0][0]);
    }

    static long[][] binPow(long[][] mat, long n) {
        long[][] res = identity();

        while (n > 0) {
            if ((n & 1) > 0) res = multiply(res, mat);
            mat = multiply(mat, mat);
            n >>= 1;
        }

        return res;
    }

    static long[][] identity() {
        return new long[][]{
                {1, 0},
                {0, 1},
        };
    }

    static long[][] baseMatrix() {
        return new long[][]{
                {1, 1},
                {1, 0},
        };
    }

    static long[][] multiply(long[][] m1, long[][] m2) {
        return new long[][]{
                {(m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD, (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % MOD},
                {(m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % MOD, (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % MOD}
        };
    }
}

2. 풀이 [C++]

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

using Matrix = vector<vector<long long>>;

constexpr int MOD = 1000000;

Matrix identity() {
    return {{1, 0}, {0, 1}};
}

Matrix base_matrix() {
    return {{1, 1}, {1, 0}};
}

Matrix multiply(const Matrix& m1, const Matrix& m2) {
    return {{(m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD, (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % MOD},
            {(m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % MOD, (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % MOD}};
}

Matrix binpow(Matrix mat, long long n) {
    Matrix res = identity();

    while (n > 0) {
        if (n & 1) res = multiply(res, mat);
        mat = multiply(mat, mat);
        n >>= 1;
    }

    return res;
}

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

    long long n;
    cin >> n;

    if (n == 0) {
        cout << 0;
        return 0;
    }

    Matrix res = binpow(base_matrix(), n - 1);
    cout << res[0][0];
}

---