[알고리즘-자바] 프로그래머스 연습문제 > 피보나치 수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12945?itm_content=course14743 

프로그래머스

언어

자바 Java

로직

제한 사항이 2 <= n  <= 100,000입니다. 재귀함수를 사용할 시에 depth 때문에 분명 StackOverFlow가 발생할 듯합니다. 따라서 재귀함수 + dp를 사용하여 해결하였습니다.

 

메모이제이션 배열 선언

한 번 답을 구했으면 추후에 다시 구하지 않도록 하기 위하여 메모이제이션 배열을 선언 및 초기화합니다. 피보나치 수열의 경우 n이 커질수록 값이 매우 커집니다. 따라서 long 타입으로 사용해야 하지만, 최종적으로 1234567을 나눈 나머지를 반환하는 게 문제이기 때문에 int 타입을 사용해도 됩니다.

int[] dp = new int[n + 1];
Arrays.fill(dp, -1);

피보나치 함수

피보나치의 종료 조건을 작성합니다. 이미 메모이제이션에 저장된 값이거나 0 또는 1일 때 값을 그대로 반환합니다.

if(dp[num] != -1)
    return dp[num];
if(num == 0 || num == 1)
    return num;

위의 두 가지 조건을 만족하지 않는다면 피보나치 함수를 다시 호출합니다.(재귀호출)

return fibonacci(dp, num - 1) + fibonacci(dp, num - 2);

메모이제이션 배열에 값 저장

for(int num = 2; num <= n; num++) {
    dp[num] = fibonacci(dp, num) % 1234567;
}

---

코드

import java.util.Arrays;

class Solution {
    public int solution(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);

        for(int num = 2; num <= n; num++) {
            dp[num] = fibonacci(dp, num) % 1234567;
        }

        return dp[n];
    }

    private int fibonacci(int[] dp, int num) {
        if(dp[num] != -1)
            return dp[num];
        if(num == 0 || num == 1)
            return num;

        return fibonacci(dp, num - 1) + fibonacci(dp, num - 2);
    }
}