[프로그래머스] 피보나치 수 - 자바(Java), 메모이제이션

문제

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

풀이

n이 최대 100000이기 때문에 엄청나게 큰 수가 만들어지게 되어 일반적인 피보나치를 계산하는 로직으로는 오버플로우가 발생하게 된다. 그렇기 때문에 fibo[n]%1234567 = (fibo[n-1] + fibo[n-2])%1234567 식을 활용하여 코드를 작성한다. 또한 메모이제이션을 사용하여 시간 초과를 방지한다.

import java.util.*;

class Solution {
    int[] fibo;

    public int solution(int n) {
        fibo = new int[n+1];

        return dfs(n);
    }

    private int dfs(int n) {
        if(fibo[n] > 0) return fibo[n];

        if(n == 0) return 0;

        if(n == 1) return fibo[1] = 1;

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