알고리즘) Fibonacci (피보나치)

long long solution(int n){

        return fibo(n);
    }

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

n값 커지면 시간제한 걸림.

long long solution(int n){

        int i;
        long long head = 1;
        long long mid = 1;
        long long rear = 0;
        long long tmp = 0;
        // 3 5 8
        // 5 8 13
        for(i=0;i<n;i++) {
            tmp = head;
            head = mid+head;
            rear = mid;
            mid = tmp;
        }
        return rear;
    }

배열로 쓰면 공간은 더 써도, 값 넣었다 뺐다 안해도 될듯.

long long solution(int n){
        long long F[81];
        F[0]=0;
        F[1]=F[2]=1;
        for(int i=3;i<=n;i++){
            F[i] = F[i-2]+F[i-1];
        }
        return F[n];
    }