[LV2/JAVA] 피보나치 수

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

프로그래머스

 

 

1. 재귀함수(recursive)로 풀면 입력값이 클 경우 메모리차지를 많이 하고 시간복잡도가 증가한다.

2. 중복연산을 없애는 dynamic programming을 해야한다.

3. 첫번째와 두번째 경우는 미리 값을 초기화하고 시작한다.

4. 오버플로우를 방지하기 위해서 각 연산에 1234567의 나머지 연산을 해야한다.

 

내 풀이

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