[백준] 11727 2xn 타일링 2

문제 출처: www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

: 2xn 직사각형을 1x2, 2x1과 2x2 타일로 채우는 방법의 수이다.

: 먼저 점화식을 구해보면 F(n) = F(n-1) + 2F(n-2)가 된다.

 

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		int[] D = new int[N+2];
		D[1] = 1;
		D[2] = 3;
		for(int i = 3; i < N+1; i++) {
			D[i] = (2*D[i-2] + D[i-1])%10007;
		}
		System.out.println(D[N]);
	}
}