프로그래머스 - 피보나치 수 문제 (자바)

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

코딩테스트 연습 - 피보나치 수

 

일반적인 피보나치 수에 메모제이션을 사용하면 풀 수 있습니다.

조심해야하는 부분은 숫자의 범위인데 n이 100,000 까지 가능해서 long의 범위를 뛰어 넘게 됩니다..

그래서 메모제이션할때 부터 나눈 나머지로 셋팅하였습니다.

class Solution {
    public static int[] dp;
    public int solution(int n) {
        dp = new int[n + 1];
        return fibo(n) % 1234567;
    }

    public static int fibo(int n) {
        if (n == 0) {
            return 0;
        }

        if (n <= 2) {
            return 1;
        }

        if(dp[n] != 0) {
            return dp[n];
        }

        return dp[n] = (fibo(n - 1) + fibo(n - 2)) % 1234567;
    }
}