실버III. 백준 11727 2 x N 타일링 2

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

11727번: 2×n 타일링 2

 

import java.util.Scanner;

public class Main {

	static int N;
	static int dp[];
	
	public static void main(String[] args) {
		solve();
	}
	
	
	public static void solve() {
		input();
		dp();
	}
	
	public static void input() {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		dp = new int [N + 1];
		sc.close();
	}
	
	
	public static void dp() {
		if(N == 1) {
			System.out.println(1);
			return;
		}
		if(N == 2) {
			System.out.println(3);
			return;
		}
		
		dp[1] = 1;
		dp[2] = 3;
		
		for(int i = 3; i <= N; i++) {
			dp[i] = dp[i - 1] + dp[i - 2] * 2 % 10007;
		}
		
		System.out.println(dp[N]);
	}
	
}