4회차 - 알고리즘 기록 : 피보나치 나머지

📌피보나치 나머지

 피보나치 수열이란 0, 1부터 시작해서 이 전의 두 값을 더해 새로운 값을 만들어나가며 전개되는 수열이다.

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

 피보나치 수열은 규칙이 간단하고 수학적으로 다양한 특징이 있기에 자주 사용되는 수열 중 하나이다. 하지만 수열이 진행될 수록 숫자가 급격히 커지기 때문에 손으로 계산하기에는 쉽지 않은 수열이다.

 피보나치 수열과 8자리 전화번호의 관련성을 연구하고 있던 지애는 손으로 하던 계산을 프로그램으로 대체하기 위하여 당신에게 도움을 요청했다. 지애를 도와주기 위하여 어떤 수 N이 주어졌을 때, N번째 피보나치 수의 마지막 8자리 숫자를 정수형태로 출력하는 프로그램을 작성해주자.

 예를 들어서 실제 수열의 값이 1,000,283,859이라면 283859만 출력하면 된다. (가장 앞의 0은 생략하고 정수처럼 출력한다)

 

 

입력 형식

 첫 줄에는 테스트케이스의 수 T가 1이상 10만 이하의 자연수로 주어진다.

각 테스트케이스의 입력은 한 줄로 구성되며, 1이상 100만 이하의 자연수 N이 공백없이 주어진다.

 

출력 형식

 각 테스트케이스별로 한 줄에 정답을 출력한다. 피보나치 수열의 N번째 숫자를 공백없이 정수형태로 출력한다.  단, 숫자 가장 앞의 0들은 생략한다. 

단, 피보나치 수열의 0번째 숫자는 0이고, 1, 2번째 숫자는 1이다.

 

예시

- 입력

10
1
2
3
4
5
6
7
8
9
10

 

- 출력

1
1
2
3
5
8
13
21
34
55

 

코드 풀이 

/**
 * 피보나치 수열의 1~n번째 항을 배열에 저장하여 반환해주는 함수
 * * 단, 항의 가장 뒤 8자리만을 저장한다.
 * @param n
 * @return fibo[i] := 피보나치 수열의 i번째 항
 */
public static int[] makeFibonacciTable(int n) {
  int[] fid = new int[n + 1];

  fid[0] = 0;
  fid[1] = 1;

  for( int i = 2; i <= n; i++ ){
      fid[i] = (fid[i-1] +fid[i-2]) % 100000000;
  }
  return fid;
}

/**
 * 피보나치 수열의 n번째 항을 반환하는 함수
 * 단, 항의 가장 뒤 8자리만을 반환한다.
 * @param n
 * @return
 */
public static int getFibo(int n){
    return makeFibonacciTable(n)[n];
}