[C++] BOJ 11444 - 피보나치 수 6

BOJ 11444 - 피보나치 수 6 (https://www.acmicpc.net/problem/11444)

 

01. 🔎 문제 탐색

n: 피보나치 수의 순서
n=0, 피보나치 수 = 0
n=1, 피보나치 수 = 1

n의 최대는 1e18로 long long 사용

피보나치 수를 1e9+7로 모듈러 연산하여 출력

01-1. 가능한 시간 복잡도

각 피보나치 수에 대해 선형탐색 시, O(N)의 시간 복잡도를 가지더라도 TLE 발생
따라서, 시간 복잡도 O(log N) 이하로 구현

01-2. 알고리즘 선택

전이행렬을 이용한, 분할 정복으로 구현

02. 📝 코드 설계하기

피보나치 수열의 점화식을 나타내면 아래와 같음

점화식을 행렬로 변환하면 아래와 같이 변환할 수 있음

 

V(n)과 A를 왼쪽과 같이 정의하면,
위의 행렬 식을 아래와 같이 변환할 수 있음

 

 V(n) = A^1 * V(n-1) 
 = A^(n-1) * V(1) 

위의 식을 풀어쓰면,

 

 

따라서, (A^n-1)의 0번째가 n번째 피보나치 수, 1번째가 n-1번째 피보나치 수를 나타낸다는 것을 알 수 있음

위의 과정을 코드로 나타내면 아래의 순서를 따를 수 있음

1. n을 입력
2. 행렬 A에 대해서 정의
3. A^n을 구함
   1. A^(n/2) * A^(n/2) 을 구하는 과정을 재귀적으로 구현, O(log n)을 따를 수 있도록 함
4. A^n의 결과의 0번째 수는 n+1의 피보나치 수를 가리키고, 1번째 수는 n번째 피보나치 수를 가리킴

 

03. 🛠️ 시도별 수정

1회차

• 지수를 n-1로 계산하여, n=1 일 경우에 제대로 된 출력을 하지 못 함

2회차

 

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;

const ll MOD = 1e9 + 7;

matrix operator*(const matrix& a, const matrix& b){
  int N = a.size(), M = b.size(), K = b[0].size();
  matrix res = matrix(N, vector<ll>(K));

  for(int i = 0; i < N; i++)
    for(int j = 0; j < K; j++)
      for(int l = 0; l < M; l++)
        res[i][j] = (res[i][j] + a[i][l] * b[l][j]) % MOD;

  return res;
}

matrix pow(matrix a, ll n){
  if(n == 1) return a;

  const matrix half = pow(a, n / 2);
  matrix res = half * half;
  if(n % 2 == 1) res = res * a;

  return res;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  matrix A = {
    {1, 1},
    {1, 0}
  };

  ll n;
  cin >> n;

  matrix res = pow(A, n);

  cout << res[0][1] << "\n";

  return 0;
}