[프로그래머스 Level2] 피보나치 수

📝 피보나치 수

문제 설명

피보나치 수

해결 방법

많이 풀어본 유형의 문제라서 익숙하게 재귀로 해결하고 제출해 보았다.

#include <string>
#include <vector>

using namespace std;

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

test case 7부터 시간초과가 나면서 틀렸다.
재귀호출 말고 반복문으로 코드를 수정했더니 통과했다.
피보나치 수를 1234567로 나눈 값을 반복문을 통해서 배열에 저장하고 리턴해준다.
n(2 <= n <= 100000)값이 점점 커질 때 재귀 호출보다 반복문을 사용하는 것이
속도가 빠르다는 것을 깨달았다.

💻소스코드

#include <string>
#include <vector>

using namespace std;

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