[LeetCode] Fibonacci Number

오늘은 피보나치 배열. 재귀함수는 늘 헷갈린다. 이러는게 맞나? 이래도 되나? 그런 느낌.

Fibonacci Number - LeetCode

 

처음 푼 방법 - 재귀함수 써보기. 런타임이 7~8ms 나왔다.

class Solution {
    public int fib(int n) {
        if(n<=1){
            return n;
        }else{
            return fib(n-1)+fib(n-2);
        }
    }
}

 

고쳐본 방법 - 아예 피보나치 계산법을 코드로 풀어보았다. 이쪽이 훨씬 런타임이 빨랐다. 0ms

class Solution {
    public int fib(int n) {
        if(n<=1){
            return n;
        }
        
        int res=0;
        int a=0, b=1;
        for(int i=0; i<n-1; i++){
            res=a+b;
            a=b;
            b=res;
        }
        return res;
    }
}

 

왜 n은 30까지일까? 

• n=50일 때: -298632863
• n=100일 때: -980107325
• n=500일 때: 315178285