2×n 타일링 2

문제

11727번: 2×n 타일링 2

문제 설명

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

제한 사항

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

입출력 예

입력	출력
2	3
8	171
12	2731

아이디어

보다 보니까 홀수면 두 번째 전 값 4 + 1이 되고 짝수면 바로 직전 값 2 + 1이 되는 규칙 발견

제출 코드

import java.io.IOException;
import java.util.Scanner;

public class three11727 {
    private int[] dp = new int[10001];

    public void solution() throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 3;
        for (int i = 2; i < 10001; i++) {
            if (i % 2 == 0) {
                dp[i] = (dp[i - 1] * 2 + 1) % 10007;
            } else {
                dp[i] = (dp[i - 2] * 4 + 1) % 10007;
            }
        }
        System.out.println(dp[n]);
    }

    public static void main(String[] args) throws IOException {
        new three11727().solution();
    }
}