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

개요

이 글은 백준 11444번 피보나치 수 6 문제를 풀이한다.

요약

$n$을 입력받아 $n$번째 피보나치 수를 $1,000,000,007$로 나눈 나머지를 출력하라.

입력 조건

$1 \leq n \leq 10^{18}$

분석

일반적인 피보나치 수열은 다음과 같이 정의된다.

\[F_{n} = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F_{n-1} + F_{n-2} & \text{if } n \geq 2 \end{cases}\]

주어진 $n$의 범위가 매우 크기 때문에, 일반적인 피보나치 수열을 구하는 방법으로는 시간 초과가 발생한다. 따라서, 이 문제를 효율적으로 해결하기 위해 다른 방법을 생각해야 한다.

풀이

피보나치 수열의 특성을 이용하여, 피보나치 수를 행렬의 거듭제곱 형태로 나타낼 수 있다. 이 방식을 이용하면, 피보나치 수열을 $\mathcal{O}(\log N)$의 시간복잡도로 구할 수 있다. 위의 피보나치 수열의 정의를 이용하여, 다음과 같은 식이 성립한다.

\[\begin{cases} F_{n+1} = F_{n} + F_{n-1} \\ F_{n} = F_{n-1} + F_{n-2} \end{cases}\]

이를 행렬로 표현하면 다음과 같다.

\[\begin{pmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n} & F_{n-1} \\ F_{n-1} & F_{n-2} \end{pmatrix}\]

여기서, 수학적 귀납법을 이용하면 이 식을 일반화할 수 있다.

\[\begin{pmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n\]

이를 이용하여 행렬 거듭제곱을 계산하면 피보나치 수를 구할 수 있다.

예시 답안

#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;
using Matrix = vector<vector<long long>>;

// 2x2 행렬 곱셈
Matrix matmul(const Matrix& a, const Matrix& b) {
  Matrix c(2, vector<long long>(2));
  for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) {
    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
  }
  return c;
}

// 2x2 행렬 거듭제곱
Matrix matpow(Matrix base, long long exp) {
  Matrix ret(2, vector<long long>(2, 0));
  for (int i = 0; i < 2; i++) ret[i][i] = 1; // 단위 행렬
  while (exp) {
    if (exp & 1) ret = matmul(ret, base);
    base = matmul(base, base);
    exp >>= 1;
  }
  return ret;
}

void solve(void) {
  long long n; cin >> n;

  cout << matpow({{1, 1}, {1, 0}}, n)[0][1];
}

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

  solve();
  return 0;
}

원본 소스 코드는 Hiyabye/Baekjoon - 11444.cpp 에서 확인할 수 있다.

문제 해결 팁

재귀를 이용한 피보나치 수열 구현은 시간복잡도가 $\mathcal{O}(2^N)$으로 매우 느리다. 따라서 이 방법은 사용하지 않는 것이 좋다.

반복문을 이용한 DP를 사용하여 피보나치 수열을 구현하면 시간복잡도가 $\mathcal{O}(N)$으로 재귀보다 빠르다. 하지만, $n$의 범위가 매우 크기 때문에 여전히 시간 초과가 발생한다.

행렬 거듭제곱을 이용한 피보나치 수열 구현은 시간복잡도가 $\mathcal{O}(\log N)$으로 앞의 방법들보다 훨씬 빠르다. 따라서, 매우 큰 $n$에 대해서도 빠르게 피보나치 수를 구할 수 있다.

마무리

도움이 되었다면 반응이나 댓글을 남겨주시면 감사하겠습니다.

추가적인 의견이나 피드백 또한 언제든지 환영입니다! :)