백준 Java 11727_ 2xn 타일링 2

• n-1의 타일에 2x1 타일이 세로로 하나 붙은 형태
• n-2의 타일에 2x1 타일이 가로로 2개 부터있거나, 2x2 타일이 붙은형태를 가진다.
• 점화식은 dp[n]=dp[n−1]+2×dp[n−2]

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

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

        int k = Integer.parseInt(br.readLine());

        int[] dp = new int[1001];
        dp[1]=1;
        dp[2]=3;
        for (int i = 3; i <= k; i++) {
            dp[i] =(dp[i-1] + 2 * dp[i-2]) % 10007;
        }
        System.out.println(dp[k]);

    }
}