BOJ 11726번 2*N 타일링

package BOJ;

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

/**
 * BOJ 11726
 * https://www.acmicpc.net/problem/11726
 */
public class TwoNTiling_11726 {

    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // D(n) = 2n : 2n 면적의 경우의 수
        // 마지막 블럭을 놓을 수 있는 경우의 수는 2가지다.
        // (1x2)블럭 2개 또는 (2x1)블럭 1개
        // (1x2)블럭 2개를 놓는다면 남은 블럭의 면적은 2(n-2)
        // (2x1)블럭 1개를 놓는다면 남은 블럭의 면적은 2(n-1)
        // D(n) = D(n-1) + D(n-2)

        arr = new int[1000+1];
        System.out.println(solve(n));

    }

    private static int solve(int n){
        arr[1] = 1;
        arr[2] = 2;

        for(int i=3; i<=n; i++){
            arr[i] = arr[i-1] + arr[i-2];
            arr[i] %= 10007;
        }

        return arr[n];
    }

}