[백준] 11727 2xn타일링2

11726 문제와 유사한 문제인데, dp[n-2]값이 2x1짜리 2개, 2x2짜리 1개씩 붙어서 두 배씩 증가하므로 점화식이 조금 달랐다. 그 외에는 다른 점이 없는 문제
점화식 : dp[n-2] * 2 + dp[n-1]

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 N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+2];

        dp[1] = 1;
        dp[2] = 3;

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