알고리즘

프로그래머스 피보나치 수 (JAVA)

박카스마시며코딩 2022. 6. 28. 17:34

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

 

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

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) =

programmers.co.kr

 

저는 해당 문제를 DP를 이용하여 문제를 해결하였습니다.

DP를 통해 이전에 계산한 값이라면 바로 그 값을 리턴하여 중복적인 계산을 하지 않도록 하였습니다.

 

class Solution {
    private static final int LIMIT = 1234567;
    private static final int NOT_VALID = 0;
    public int solution(int n) {
        int[] dp = new int[n+1];
        int answer = fib(n,dp);
        return answer;
    }
    private int fib(int num,int[] dp){
        if(num == 0 || num == 1){
            return num;
        }
        if(dp[num] != NOT_VALID){
            return dp[num];
        }
        return dp[num] = (fib(num-1,dp) + fib(num-2,dp)) % LIMIT;
    }
}