타일링 방법의 수 세기 (난이도: 하)

1. 문제 설명

(1) 2xN 크기의 사각형을 2x1 크기의 타일로 채우는 방법의 수를 계산하는 문제가 있다고 하자.

 

(2) 타일들은 서로 겹쳐서는 안 되고 90도로 회전해서 쓸 수 있다.

 

(3) 예를 들어, N=5라고 하면, 아래의 그림과 같이 여덟 가지의 방법이 있다.

 

 

 

(4) 이때 N의 최댓 값이 100이라고 할 때 타일을 채우는 방법의 수를 찾는 프로그램을 작성하시오.

 

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 입력의 첫 줄에는 테스트 케이스의 수 C가 주어진다.

(2) 그 후 각 줄에 사각형의 너비(1<=N<=100)이 주어진다.

 

출력 조건

X

 

 

입력 예제

2

5

50

 

 

출력 예제

8
365010934

 

 

 

 

3. 제약 조건

X

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1) 더 이상 사각형을 쪼갤 수 없는 경우

 

 

 

 

6. 코드

public class TILING2 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int MOD=1000000007;

    private static int[] cache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[101];

            sb.append(solve(Integer.parseInt(sc.readLine()))+"\n");
        }
        System.out.println(sb);
    }
    private static int solve(int width) {
        // 기저 사례(1): 더 이상 사각형을 쪼갤 수 없는 경우
        if(width<=1) return 1;

        if(cache[width]!=0) return cache[width];

        // 가로 두 칸을 없앨 경우: solve(width-2)
        // 세로 두 칸을 없앨 경우: solve(width-1)
        return cache[width] = (solve(width-1) + solve(width-2)) % MOD;
    }
}

 

 

 

 

7. 점화식