피보나치 나머지

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 피보나치 나머지
public class Main {

    // 피보나치 수를 N번 구해놓으면?
    public static int[] fibonacci = new int[1000001];

    public static void main(String[] args) throws IOException {
        // 피보나치 수열과 8자리 전화번호의 관련성 연구
        // 어떤 수 N이 주어졌을 때, N번째 피보나치 수의 마지막 8자리 숫자를
        // 정수형태로 출력하는 프로그램을 작성
        // 1이상 100만 이하의 자연수 N

        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int[] tests = new int[T];
        for(int i = 0; i < T; i ++){
            tests[i] = Integer.parseInt(br.readLine());
        }

        // 점화식
        createdFibonacci();
        for(int i = 0; i < T; i ++){
            System.out.println(fibonacci[tests[i]]);
        }
    }

    private static void createdFibonacci() {
        fibonacci[0] = 0;
        fibonacci[1] = fibonacci[2] = 1;
        for(int i = 3; i <= 1000000; i++){
            fibonacci[i] = (fibonacci[i - 2] + fibonacci[i - 1]) % 100000000;
        }
    }
}

해석

1. 피보나치 수를 백만번 계산한다. 

2. 피보나치 수를 그대로 출력해준다.

 

해맸던 점

1. 처음에는 8자리 숫자만 출력한다. 여기에서 100000000 을 %해주는 로직을 생각해내지 못해서 int 범위를 넘어서 잘못된 정답을 출력했다.