[프로그래머스] 피보나치 수 자바(Java)

문제 설명

 

피보나치 수는 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

 

---

 

코드 설명

 

재귀함수를 사용하는 방법도 있으나, 저는 배열로 해결했습니다. 피보나치 수를 담을 배열 fibo를 n+1 크기로 선언하고 0번 인덱스에 0, 1번 인덱스에 1을 미리 담아줍니다. 이후 반복문을 통해 fibo[i-2]와 fibo[i-1]을 더한 값을 1234567로 나눈 나머지를 넣어줍니다. 이에 따라 return fibo[n]을 하면 n번째 피보나치 수를 알아낼 수 있습니다.

 

초기에는 피보나치 수에 대한 1234567 나머지 연산을 return에서 처리했었습니다. (return fibo[n] % 1234567) 하지만 7번 테스트부터 쭉 실패가 나오는 것을 볼 수 있었습니다. 왜일까요?

 

바로 int의 범위 때문입니다. int형 변수는 -21,4748,3648 ~ 21,4748,3647까지의 값을 저장할 수 있는데요, 해당 범위를 넘어가면 올바른 연산이 이루어지지 않습니다. 따라서 이미 잘못된 값에 나머지 연산을 하니 올바른 결과가 나올 수 없었습니다. 따라서 나머지 연산을 반복문 안에서 실행함으로써 문제를 해결할 수 있었습니다.

 

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];
    }
}