2×n 타일링 2

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

// 코드

import java.util.*;
import java.io.*;
 
public class Main{
  
  public static void main(String[] args) throws Exception {
    
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int n = Integer.parseInt(st.nextToken());
    
    int[] dp = new int[n+1];
    dp[0] = 1;
    dp[1] = 1;
    
    for(int i=2; i<n+1; i++) {
      dp[i] = (dp[i-1] + 2 * dp[i-2]) % 10007; 
    }
    
    bw.write(String.valueOf(dp[n]));
        
    br.close();
    bw.flush();
    bw.close();
  }
  
}