BOJ 11726 2xn 타일링

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

public class Main {
    static int N;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());


        if(N==1){
            System.out.println(1);
        }else if(N==2){
            System.out.println(2);
        }else if(N==3){
            System.out.println(3);
        }else{
            dp = new int[N+1];
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 3;

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

            System.out.println(dp[N]%10007);
        }
    }
}