피보나치 수/C++

프로그래머스 - 피보나치 수

프로그래머스

 

아래처럼 재귀호출을 사용했더니 시간 초과가 떠서 배열로 풀었다.

#include <string>
#include <vector>

using namespace std;

int Fibonacci(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else return Fibonacci(n - 1) + Fibonacci(n - 2) % 1234567;
}

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

 

풀이 방법

1. int형 벡터 컨테이너 Fibonacci를 선언한다.

2. n은 2 이상인 자연수이므로 0, 1 인덱스에 각각 F(0), F(1)에 해당하는 값을 넣어준다.

3. 이후 2부터 n까지 F(i - 1) + F(i - 2) % 1234567을 담는다. (오버플로우 방지)

4. n번째 피보니치 수를 1234567로 나눈 나머지를 리턴 

#include <string>
#include <vector>

using namespace std;

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