[프로그래머스] 피보나치 수

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

---

Think🤔

처음에 재귀함수를 만들어서 반복문으로 돌게했는데 이렇게 하면 계속해서 함수를 타기 때문에

시간 초과가 나온다.

public class pibo {
    public static void main(String[] args) {
        int n = 2000;
        int answer = 0;

        answer = pibo(n-2) + pibo(n-1);

        System.out.println(answer);
    }

    public static int pibo(int num){
        if(num <= 1){return num;}

        return pibo(num-2) + pibo(num - 1);
    }
}

// 시간 초과 재귀적으로 타게 하면

그 다음 방법으로 재귀 말고 배열을 생성해서 캐쉬를 이용해서 풀었다.

반복문은 2부터 시작하게 하고 , 배열 0 , 1은 미리 선언해둔다.

 

이런식으로 하게 되면

반복문을 돌면서

 

pibo[10] = pibo[9] + pibo[8] 이렇게 되면 해당 pibo[9]는 그 전 반복문을 이용해서 저장했기 때문에 함수를 다시 타지 않고 풀 수 있다. 

---

Solution✍

class Solution {
    public int solution(int n) {
        return pibo(n);
    }

    public static int pibo(int num){
        int cache[] = new int[num+1]; // 캐쉬 남겨둠

        if(num <= 1){return num;}

        cache[0] = 0;
        cache[1] = 1;

        for(int i=2; i<=num; i++){
            cache[i] = (cache[i-1] + cache[i-2]) % 1234567;
        }

        return cache[num];
    }
}

---

Review🤩

% 1234567을 하게 되어있는데, 이는 피보나치 수로 더하게 되면 값이 기하급수적으로 커져서, int의 범위를 빠르게 넘어갈 수 있기 때문... int의 범위는 –2,147,483,648 ~ 2,147,483,647 이렇게 되어 있는데 2,147,483,647 에서 1바이트만 커져도

– 2,147,483,648 가 될 수 있기 때문!! 

더 자세한 설명은 찾아보시길..

---