[프로그래머스/C++]Lv.2 - 피보나치 수

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12945

내 풀이

재귀함수의 대표적인 예로 나오는 피보나치 수다. 하지만 그 재귀함수를 사용하면 수가 클 경우 ( 이 문제의 최대 범위는 100000 ) 횟수가 너무 많아지므로 오류가 난다.
그래서 for문과 배열을 이용하여 수를 구하였다.

내 코드

#include <string>
#include <vector>

using namespace std;

int fibonacci(int n)
{
    int F[100001];
    F[0] = 0;
    F[1] = 1;
    F[2] = 1;
    for(int i = 3; i <= n; i++)
        F[i] = (F[i - 1] + F[i - 2]) % 1234567;
    return F[n];
}

int solution(int n) {
    int answer = 0;
    n = fibonacci(n);
    answer = n;
    return answer;
}

다른 사람의 풀이

#include<iostream>
#include<vector>
using namespace std;

typedef vector<vector<long long>> matrix;

matrix operator* (matrix &a, matrix &b) {
  int n = a.size();
  matrix c(n, vector<long long>(n));
  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
      for(int k=0; k<n; k++)
        c[i][j] += a[i][k] * b[k][j];
  return c;
}

long long fibonacci(int n)
{
  matrix res = {{1, 0},{0, 1}};
  matrix fib = {{1, 1},{1, 0}};
  while(n) {
    if(n%2==1) res = res * fib;
    fib = fib * fib;
    n *= 0.5;
  }
  return res[0][1];
}

int main()
{
    int testCase = 10;
    long long testAnswer = fibonacci(testCase);

    cout<<testAnswer;
}

다른 사람의 풀이 해석

다양한 답이 있다. 위의 답은 행렬 곱을 이용한 풀이인거 같은데 아직 이해는 하지 못했다.
재귀함수는 호출 횟수가 너무 많아져서 작은 수가 아니면 활용하지 못할 것 같다.
https://sbinroom.tistory.com/entry/C%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4-%EA%B5%AC%ED%98%84-fibonacci
다양한 방법과 공식도 있으니 참고해보자.