#12945 피보나치 수열

programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

재귀함수가 이해가 잘 안돼서 재귀 관련 문제를 찾다가 풀게 되었다.

 

#include <string>
#include <vector>

using namespace std;

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

그래도 피보나치 수열은 쉽구나! 하다가

 7번부터 시간 초과.. 

 

알고보니 재귀로 풀면 메모리 초과때문에 안되는 거였다.

항상 재귀는 배신을 해....

 

결국 이렇게 풀었다

#include <string>
#include <vector>

using namespace std;

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

 

백준 문제는 항상 이렇단 말이지.😒

인생이란 원래 자기 생각대로 되지 않는 법이란다..