509. Fibonacci Number

문제출처

피보나치 수열이 있을 때 수열의 n번째 값을 구하는 문제.

옛날에 수학시간에 봤던 기억은 났지만 기억이 잘 안나서 그냥 주어진 F(n)식을 이용해서 풀었다.

[처음 푼 코드]

class Solution {
    public int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int[] arr = new int[31];
        arr[0] = 0;
        arr[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }
        
        return arr[n];
    }
}

 

다른 사람들이 푼 코드를 보고 느낀 건 n이 1이하일 때는 n을 리턴해주는 걸로 단순화 할 수 있었다.

if (n == 0) return 0;

if (n == 1) return 1;

--------------------------

if (n <= 1) return n;

 

또한 배열의 선언 없이 단순히 변수 두개의 값을 담아서 할 수도 있었다.

나의 경우는 어차피 n이 30개 이하라는 조건이 주어졌기 때문에 단순히 31 크기인 배열을 생성했다.

허나 만약 n이 이보다 훨씬 커진다면 내가 작성한 코드는 공간복잡도가 n이므로 쓸 데 없는 공간을 차지할 것처럼 보인다.

 

[수정한 코드]

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