11727.2xn타일링2

문제

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

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

## 입력

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

## 출력

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	68465	40719	32702	58.894%

https://www.acmicpc.net/problem/11727

풀이

코드

import java.util.Scanner;  

public class _2xn타일링2 {  

    static int[] dp = new int[1001];  

    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  

        int n = sc.nextInt();  

        System.out.println(tiling(n));  
        sc.close();  
    }  

    public static int tiling(int n){  

        if(n == 1) return 1;  
        if(n == 2) return 3;  

        if(dp[n] == 0){  
            dp[n] = (tiling(n-1) + (tiling(n-2) * 2)) % 10007;  
        }  
        return dp[n];  
    }  
}