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

✅ LV. 2

✏️ 1차 솔루션

재귀함수로 피보나치 구현

int fibo(int n) {
	if(i<=1) return n;
    else return fibo(n-1) + fibo(n-2);
}

🚨 1차 trouble

7~14 test case 시간초과 발생
재귀함수로 별도의 함수를 구현한 것에 더하여 문제의 조건 중 피보나치 수를 1234567 로 나눈 나머지를 구하라는 조건의 의도를 파악하지 못했다.
int 범위를 초과하는 것을 방지하기 위해 각각의 피보나치 수를 1234567 로 나눴어야 했다.

✏️ 2차 솔루션

재귀함수 대신 각 피보나치 수를 벡터에 저장해서 구현하기

✏️ 최종 코드

#include <vector>

using namespace std;

int solution(int n) {
    vector<int> v;
    
    for(int i=0;i<=n;i++) {
        if(i<=1) v.push_back(i);
        else {
            int k=(v[i-1]+v[i-2])%1234567;
            v.push_back(k);
        }
    }
    
    return v[n];
}

0 과 1 에 대한 피보나치 수를 제외하고 다른 수에 대한 피보나치 값은 벡터에 저장하기 전에 1234567 로 나눈 나머지 값을 저장해주었다.