[LeetCode/Easy] 509. Fibonacci Number

1. Input

1) 정수 n

 

2. Output

1) F(n)을 계산한 결과

2) F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n은 2 이상의 정수)

 

3. Constraint

1) 0 <= n <= 30

 

4. Example

Input: n=4 -> Output: 3

설명: 0, 1, 1, 2, 3이므로 3을 반환

 

5. Code

1) 첫 코드(2022/06/18)

if(n==0) return 0;

if(n==1 || n==2) return 1;

int a=1, b=1, c=0;
for(int i=3 ; i<=n ; i++){
    c = a+b;
    a = b;
    b = c;
}
return c;

2) 재귀호출을 이용한 코드(2022/12/01)

int result = 0;
    if(n<=1) result = n;
else
    result = fib(n-1) + fib(n-2);
return result;

 - 1번에 비해 느렸지만, 공간 절약이 더 되긴 했다.