[알고리즘C++]피보나치 수

오늘의 문제

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

피보나치 수

나의 풀이

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

int solution(int n) {
    vector<vector<int>> num(n, vector<int>(2, 0)); // 몫, 나머지
    num[0][0] = 0;
    num[0][1] = 1;
    num[1][0] = 0;
    num[1][1] = 1;
    for(int i=2;i<n;i++){
        num[i][1] = num[i-2][1] + num[i-1][1];
        num[i][0] = num[i-2][0] + num[i-1][0] + num[i][1]/1234567;
        num[i][1] %= 1234567;
    }
    return num[n-1][1];
}

모범 답안

long long fibonacci(int n)
{
  int i;
    long long dp[1000];
  dp[0]=0;
  dp[1]=1;

  for(i=2; i<=n; i++)
  {
    dp[i]=dp[i-1]+dp[i-2];
  }

    return dp[n];
}

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

    cout<<testAnswer;
}

배울 점

• 처음에 작성한 코드는 int의 범위를 넘어난 이유로 reject되었다. 범위를 생각해보면서 문제에 접근하도록 하자.
• 44번째 피보나치 수만 가도 2,971,215,073로 int 범위를 넘어버린다
• (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C 성질을 이용해도 되는것이었다.
• 수식으로 한번 정리해보는것도 좋을 것 같다.