BOJ 11727번 2*N 타일링2

package BOJ;

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

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

    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 면적의 경우의 수
        // 마지막 블럭을 놓을 수 있는 경우의 수는 3가지다.
        // (2x1)블럭 1개 또는 (2x2)블럭 1개 또는 (1x2)블럭 2개
        // (2x1)블럭 1개를 놓는다면 남은 블럭의 면적은 2(n-1)
        // (2x2)블럭 1개를 놓는다면 남은 블럭의 면적은 2(n-2)
        // (1x2)블럭 2개를 놓는다면 남은 블럭의 면적은 2(n-2)
        // D(n) = D(n-1) + 2 * D(n-2)

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

    }

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

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

        return arr[n];
    }

}