kingsubin

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

// # 2xn 타일링 2
public class boj_11727 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] dp = new int[1001];

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        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]);
    }
}

 

- 2xn의 타일을 채울때 마지막에 올 수 있는 타일은 세로2 타일 1개, 가로1 타일 2개, 가로세로2 타일 1개

- 이렇게 3가지 방법으로 올 수 있다.

- 세로2타일의 경우는 dp[n-1], 나머지 두 방법은 모두 dp[n-2]라서 점화식을 세워보면

- dp[n] = dp[n-1] + 2 * dp[n-2]와 같다.