BOJ 11727 2xn 타일링 2

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

/***
 * 시간제한: 1초, 메모리제한: 256MB
 * 1 <= N <= 1000
 * 아이디어: N=1일 때, N=2일 때, N=3일 때의 규칙을 찾아서 점화식을 작성하자!
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        if(2<N) {
            int[] dp = new int[N+1];
            dp[1] = 1; // 2x1 직사각형을 채울 방법은 한가지
            dp[2] = 3; // 2x2 직사각형을 채울 방법은 세가지

            for(int i=3; i<=N; i++){
                dp[i] = (dp[i-1]+2*dp[i-2])%10007;
            }

            System.out.println(dp[N]);
        }
        else if(1<N) System.out.println(3);
        else System.out.println(1);

    }
}