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

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

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

문제풀이

전형적인 DP문제 중에서 대표적인 피보나치 수열이다. 하지만 함정 아닌 함정이 있었다. 7번부터 오답이 나오는 것이었는데 문제가 숫자의 범위에 있었다 피보나치 44번째만 가도 int의 범위를 넘어서기 때문에

(A + B) % C 의 값을 (( A % C ) + ( B % C )) % C와 같다는 성질을 이용해서 풀어야 한다.

 

코드

class Solution {
    public int solution(int n) {
        int[] fibo = new int[n+1];
        fibo[0] = 0;
        fibo[1] = 1;
        
        for(int i=2; i<=n; i++){
            fibo[i] = (fibo[i-2]+ fibo[i-1]) % 1234567;
        }
        
        return fibo[n];
    }
}