baekjoon 11444:피보나치 수 6

baekjoon 11444 피보나치 수 6

11444번 피보나치 수 6

접근

피보나치를 행렬로 구하는 방법을 알고 있어야 풀 수 있는 문제이다.
/\(\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n}=\begin{pmatrix} fib(n+1)&fib(n) \\ fib(n)&fib(n-1) \end{pmatrix} /\) 이 방식을 이용하면 제곱하면서 분할정복할 수 있다.

코드

#include <iostream>
#include <array>
#define MOD 1000000007
using namespace std;
array<array<int, 2>, 2> matMul(array<array<int, 2>, 2> a, array<array<int, 2>, 2> b);
array<array<int, 2>, 2> matFib(long long int n);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  long long int n;
  cin >> n;
  array<array<int, 2>, 2> ans = matFib(n);
  cout << ans[0][1];
  
  
  return 0;
}
array<array<int, 2>, 2> matMul(array<array<int, 2>, 2> a, array<array<int, 2>, 2> b){
  array<array<int, 2>, 2> ret;
  for(int i = 0; i < 2; i++){
    for(int j = 0; j < 2; j++){
      ret[i][j] = ((long long)a[i][0] * (long long)b[0][j] + (long long)a[i][1] * (long long)b[1][j])%MOD;
    }
  }
  return ret;
}
array<array<int, 2>, 2> matFib(long long int n){
  array<array<int, 2>, 2> ret;
  if(n == 1){
    return {{{{1, 1}}, {{1, 0}}}};
  }
  if(n%2 == 0){
    ret = matFib(n/2);
    return matMul(ret, ret);
  }
  else{
    ret = matFib((n-1)/2);
    return matMul(matMul(ret, ret), matFib(1));
  }
}

배운 점

피보나치 수를 행렬로 구하는 법을 배웠다.
그리고 cpp에서 array parameter로 받거나 return 할때는
std::array를 쓰는게 cpp답게 푸는 것이라는 것을 알았다.