[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 이하인 자연수입니다.

Main Method

public static void main(String[] args) {
	int n = 5;
    int answer = 0;
    answer = getFibonacciDivisionNumber(n);
    System.out.println(answer);
}

getFibonacciDivisionNumber

public static int getFibonacciDivisionNumber(int n) {
	if (n >= 2) {                                                       // n은 2 이상이어야 한다.
    	int[] fibArr = new int[n + 1];                                  // 반복 횟수가 n + 1만큼 되어야 하기 때문에 길이를 n+1로 설정
        fibArr[0] = 0;                                                  // 피보나치 수열은 0부터 n까지
        fibArr[1] = 1;                                                  // 처음엔 1을 더해야한다.

		for (int i = 2; i <= n; i++) {                                  // 첫 값은 배열에 집어 넣었으니 2번 인덱스에 값을 집어넣기 위해 i = 2
        	fibArr[i] = (fibArr[i - 1] + fibArr[i - 2]) % 1234567;      // 피보나치 수열 공식이다. 먼저 (n-1) + (n-2)를 계산하고 1234567로 나눈 후 나머지를 저장하자
		}

		return fibArr[n];                                               // 마지막 배열 인덱스 요소에 원하는 값이 담긴다.
	}

	return n;                                                           // 아닌 경우 n을 반환
}

포인트
1. 피보나치 수열 공식을 알고 있어야한다. (나는 몰라서 찾아봤다.)
2. 배열을 사용하면 깔끔하다. (ArrayList로 해도 똑같이 할 수는 있다.)
3. 재귀로도 가능할 것 같다. 다음에 비슷한 유형이 있다면 재귀로도 풀어보자
4. 알고리즘보단 수학문제에 가까운 느낌이다. 결국 쓰는건 for문 하나 뿐..