[백준/BOJ] 11442번 홀수번째 피보나치 수의 합 (C++)

개요

이 글은 백준 11442번 홀수번째 피보나치 수의 합 문제를 풀이한다.

요약

$n$을 입력받아 피보나치 수열의 $0$번째 항부터 $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$의 범위가 매우 크기 때문에, 일반적인 피보나치 수열을 구하는 방법으로는 시간 초과가 발생한다. 따라서, 이 문제를 효율적으로 해결하기 위해 다른 방법을 생각해야 한다.

풀이

과정 1. 피보나치 수열의 합 일반화

피보나치 수열을 변형하여 다음과 같은 식을 얻을 수 있다.

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

여기서 $F_{0}$부터 $F_{n}$까지의 홀수번째 항들의 합은 다음과 같이 정리할 수 있다.

1) $n$이 홀수인 경우

\[F_{1} + F_{3} + \cdots + F_{n}\] \[= (F_{2} - F_{0}) + (F_{4} - F_{2}) + \cdots + (F_{n+1} - F_{n-1})\] \[= F_{n+1}\]

2) $n$이 짝수인 경우

\[F_{1} + F_{3} + \cdots + F_{n-1}\] \[= (F_{2} - F_{0}) + (F_{4} - F_{2}) + \cdots + (F_{n} - F_{n-2})\] \[= F_{n}\]

과정 2. 행렬 거듭제곱을 이용한 피보나치 수열 구현

피보나치 수열의 특성을 이용하여, 피보나치 수를 행렬의 거듭제곱 형태로 나타낼 수 있다. 이 방식을 이용하면, 피보나치 수열을 $\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 + (n & 1))[0][1];
}

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

  solve();
  return 0;
}

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

문제 해결 팁

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

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

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

마무리

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

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