[프로그래머스 12945] Level2 피보나치 수

문제 URL

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

프로그래머스

 

문제풀이 Key Point

• 재귀 호출에 대해 반복되는 동일 연산에 대한 처리를 고민해야한다.(시간초과와 관련됨)
• 결과를 1234567로 나누라는 요구사항이 있다.
  피보나치 수의 점화식을 세우면 F(n) = F(n-1) + F(n-2) (F(n) = 0, F(n) = 1)이다.
  따라서 (A + B)%C = ((A % C) + (B % C)) % C라는 공식을 이용할 필요가 있다.
  (또는 계산된 결과에서 나눈다면 계산 과정이 int 범위를 넘어가기 때문에 type을 long으로 선언하는 방법이 있다.)

 

Java 문제풀이

class Solution {
    private static final int FIBONACCI_REMINDER = 1234567;
    public int solution(int n) {
        int[] saved = new int[n + 1];
        int answer = fibonacci(saved, n);
        
        return answer;
    }
    
    private int fibonacci(int[] saved, int n) {
        if (n == 1) {
            saved[n] = 1;
            return 1;
        }
        
        if (n == 0) {
            saved[n] = 0;
            return 0;
        }
        
        if (saved[n] != 0) {
            return saved[n];
        }
        
        saved[n] = (fibonacci(saved, n - 2)%FIBONACCI_REMINDER+ fibonacci(saved, n - 1)%FIBONACCI_REMINDER)%FIBONACCI_REMINDER;
        return saved[n];
    }
}