[Programmers] 피보나치 수(자바)

문제

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

 

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을

완성해 주세요.

 

---

제한 사항

   -  n은 2 이상 100,000 이하인 자연수입니다.

 

---

입출력 예

n	return
3	2
5	5

 

---

입출력 예 설명

  피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

 

 

 

 

---

 

풀이

처음 작성 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] Fibo = new int[n+1];
        Fibo[0] = 0;
        Fibo[1] = 1;
        
        //F(n)까지의 각 피보나치 수 대입
        for(int i=2; i<=n; i++){
            Fibo[i] = (Fibo[i-1] + Fibo[i-2]);
        }
        answer = Fibo[n] % 1234567;
        
        return answer;
    }
}

오류가 발생했던 코드이다.

 

!문제: 주어진 테스트케이스 2개는 통과했으나, 제출 시 14개 중 7개의 테스트만 통과하였다.

!원인: Fibo의 자료형 범위를 초과했다.

 

 

Fibo의 자료형은 int이다. int는 -2,147,483,648 ~ 2,147,483,647까지의 값만을 표현할 수 있다. 

그런데 여기서 1을 더하게 되면 그 숫자는 2,147,483,647이 아닌 -2,147,483,648이 된다.

 

피보나치 수는 수가 엄청나게 빠르게 증가한다. 44번째 피보나치 수만 가도 2,971,215,073으로 int의 범위를 넘어버린다. 따라서 위의 코드처럼 Fibo에 큰 값을 넣게 되면 범위를 벗어나 예상한 값과 다른 값이 출력될 수 밖에 없다.

 

따라서, 문제에서 n번째 피보나치 수를 1234567로 나눈 나머지를 구하라는 이유는

1234567로 나눈 나머지는 항상 1234567보다 작을 수 밖에 없고, 계산한 피보나치 수를 1234567로 나눠도 원래의 피보나치 수와 완벽하게 동일한 숫자가 나오기 때문이다.

 

 

 

최종 수정 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] Fibo = new int[n+1];
        Fibo[0] = 0;
        Fibo[1] = 1;
        
        //F(n)까지의 각 피보나치 수 대입
        for(int i=2; i<=n; i++){
            // 99999와 같이 큰 수를 넣을 경우 int와 long타입의 범위를 넘어
            // 값들을 문제 조건에 맞게 1234567로 나눈 나머지로 저장
            Fibo[i] = (Fibo[i-1] + Fibo[i-2])%1234567;
        }
        answer = Fibo[n];

        return answer;
    }
}

Fibo의 자료형에 맞도록 Fibo를 계산할 때 1234567로 나눈 나머지를 저장하도록 수정했다.