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

피보나치 수

문제링크

풀이

재귀와 memoization을 활용해서 문제를 풀이하였다.
처음에 % 1234567를 마지막 결과값을 나타낼 때만 사용했었는데, overflow가 나서 결과값이 제대로 나오지 않았다.
그 이후 memo[] 저장할 때 모든 값에 % 1234567를 적용하여 문제를 해결했다.

다른 사람의 풀이의 경우 그냥 for문을 활용하여 n이 커지도록 하여 이전 값들을 더해 fibo(n)을 구하는 형식으로 빠르게 풀이 하였다.

코드

class Solution {
    public static int[] memo;
    public int solution(int n) {
        memo = new int[n + 1];

        return fibo(n);
    }
    private static int fibo(int n) {
        if (n == 0) {
            return memo[0];
        }
        if (n == 1) {
            memo[1] = 1;
            return memo[1];
        }
        if (memo[n] == 0) {
            memo[n] = fibo(n - 1) + fibo(n - 2);
        }
        return memo[n] % 1234567;
    }
}