[Java][프로그래머스-코딩테스트 level2] 피보나치 수

o 요구사항

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

 

o 코드진행

1. n번째 피보나치 수 계산하기
피보나치 수는 재귀함수를 사용하면 간단하게 구현할 수 있다.
하지만 그 효율성은 매우 떨어진다.
때문에 문제에서 주어지는 100000이하의 자연수 n번째 피보나치 수를 구하는데는
시간이 많이 소요될 뿐더러 재귀함수가 재귀함수를 끝없이 호출하는 식으로 되어 메모리가 버티질 못한다

for 문을 사용하면 재귀함수 보다 효율적인 함수를 생성할 수 있다.

 

2. 1234567로 나눈 나머지 계산하기
문제에서 1234567로 나눈 나머지를 리턴하도록 하였으므로 큰 숫자를 계산할 필요가 없다.

 

임의의 숫자 Number를 K로 나눈 나머지는, Number를 더해서 구성할 수 있는

Number1 과 Number2 의 각 나머지를 합한 값에서 K로 나눈 나머지를 구한 값과 동일하다

 

예를들어 12를 5로 나눈 나머지는 2이다
12는 4 + 8의 합으로도 구성되는데 각 나머지를 계산하면 다음과 같다
4를 5로 나눈 나머지는 4
8을 5로 나눈 나머지는 3
각 나머지를 합한 7(4+3) 을 5로 나눈 나머지는 2이다

이를 메소드에 적용하여 설계한다

o 코드설계

1. n번째 피보나치 수 계산하기

피보나치 수를 for문을 이용하여 구하는 것의 핵심은 연속한 두 숫자 a, b가 이어서 b, a+b로 이어진다는 것이다.

반복문으로 a, b에 b, a+b를 대입하여 식을 반복하면 n 번째 피보나치를 구할 수 있다.

이때 위에서 언급한 대로 1234567로 나눈 나머지만 구하면 되기 때문에 나머지를 대입해준다.

아래 코드의 경우 int형 변수 b 대신 1234567로 나눈 int형 변수 b_를 연산에 대입하는 코드로 구현하였다.

 

2. 최종 결과값 반환

getFibonacci_Remaider() 메소드(아래 코드 참조)로 구한 나머지 값이 1234567보다 큰 값이 주어질 수 있다.

결과값을 리턴하기 전, 1234567로 나눈 나머지를 다시 구한뒤 int로 변환하여 리턴한다.

 

 

o 완성코드

class Solution {
    public int solution(int n) {
    	return (int) getFibonacci_Remainder(n, 1234567) % 1234567;    	
    }
    
    double getFibonacci_Remainder(double n, double m){
    	double fibon		= 1;
    	double tmp		= 0;
    	double a		= 0;
    	double b		= 1;
    	double b_		= 0;
    	if(n == 0) {
    		return 0;
    	}
    	for(double i=0; i<n-1 ; i++) {
    		b_		= b%m;    		
    		tmp		= a;
    		a		= b_;
    		b		= tmp + b_;
    		fibon		= b;
    	}
    	return fibon;
    }
}