[Programmers]-피보나치 수

문제

피보나치 수를 구하면 되는 문제입니다.

코드

class Solution {
    long[] memo;
    public int solution(int n) {
        int answer = 0;
        memo = new long[n+1];
        memo[1] = 1;
        memo[2] = 1;
        
        answer = (int)(fibo(n)%1234567);
        
        return answer;
    }
    
    public long fibo(int n){
        if(n <= 1)
            return memo[n]%1234567;
        else if(memo[n]!=0)
            return memo[n]%1234567;
        return memo[n] = fibo(n-2)%1234567 + fibo(n-1)%1234567;
    }
}

코드 설명

피보나치는 재귀함수로 구하지만 n값이 커질수록 시간복잡도가 급속도로 커진다.

그래서 메모이제이션을 써줘야한다.

피보나치1과 2는 1이기때문에 초기값을 넣어준다.

요약

• 피보나치는 메모이제이션 쓴다.