[Programmers/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	return
3	2
5	5

---

참고 자료

피보나치 수

F(n) = F(n-2) + F(n-1)

 

코드 해석 및 전체 코드

F(0) == 0, F(1) == 1이므로 변수 f1은 F(0), f2는 F(1)으로 시작한다. 

 

n은 2부터 주어지고 F(0)과 F(1)은 미리 변수에 선언하고 시작하여 i는 2부터 시작하고 n까지 반복한다. 

 

조건에서 값을 1234567로 나눈 값을 반환하라 했는데, 

해당 문제의 질문 목록에 값을 1234567로 나누어야하는 이유를 설명해준 글이 있다.

피보나치 수 44만 해도 2,971,215,073로 int의 값을 훨씬 넘은 수라 int 내에서 해결하기 위한 문제 의도인 거 같다.

 

그래서 answer(=F(n))에 F(n-2) + F(n-1) 값을 저장할 때 1234567로 나눈 나머지 값을 저장했다.

 

피보나치 수를 구하기 위한 코드는

fn = f1 + f2; f1 = f2; f2 = fn;

으로 fn은 f(n-2) +f(n-1)이 들어가야한다.

그리고 다음 F(n+1)을 구하기 위해 f1에는 f2(F(n-1)를, f2에는 fn(F(n))을 넣어준다.

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        int f1 = 0;
        int f2 = 1;
        int d = 1234567;
        
        for(int i = 2; i <= n; i++){
            answer = (f1 + f2) % d;
            f1 = f2;
            f2 = answer;
        }
        
        return answer;
    }
}

---

github

programmers