[200904] 피보나치 수 - 연습문제(level2)

1. 문제 이해

- 피보나치 수의 정의

: F(0) = 0, F(1) = 1일 때, F(n) = F(n-1) + F(n-2)가 적용되는 수

ex> 0 1 1 2 3 5 8 13 . . . 

- n번째 피보나치 수를 1234567로 나눈 나머지를 리턴

 

 

2. 전략

(1) 첫번째 시도 : 재귀함수를 이용

    int Fibonacci(n){
        if(n == 0) return 0;
        else if(n==1) return 1;
        else    return Fibonacci(n-1) + Fibonacci(n-2);
    }

- 문제점 : 불필요한 중복 계산이 들어감(Fibonacci(n-1)을 구할 때 Fibonacci(n-2)를 한 번 더 구함)

              →  시간 초과

 

(2) 두번째 시도 : int 배열에 0~n번째 피보나치 수를 차례로 저장

- 작은 문제부터 푸는 "상향식 Dynamic Programming"

- 단, 1234567로 나눈 결과이므로 각 피보나치 수를 저장할 때 나눗셈 연산(%) 진행

 

※ 1234567로 나누는 과정이 필요한 이유

- n이 커질수록 피보나치 수는 급격히 증가 → 데이터 타입의 범위를 벗어남 → 잘못된 결과

- n 이전부터 결과가 잘못될 수도 있으니 각 피보나치수를 구할 때 1234567로 나눠줘야 됨

 

 

3. 참고 사항

 

4. 코드

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