비대칭 타일링 (난이도: 하)

( 아래의 사이트에 나오는 알고리즘을 먼저 보는 것을 추천합니다. )

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

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

 

1. 문제 설명

(1) 아래의 그림과 같이 2xN 크기의 직사각형을 2x1 크기의 타일로 채우려고 한다.

 

 

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

* 단 이 타일링 방법은 좌우 대칭이어서는 안 된다.

 

(3) 위의 그림은 2x5 크기의 직사각형을 채우는 비대칭 타일링 방법 여섯 가지를 보여준다.

 

(4) 그러나 아래 두 개의 그림에서는 좌우대칭이기 때문에 세지 않습니다.

 

(5) 2xN에서 N이 주어질 때 가능한 비대칭 타일링 방법의 수를 찾는 프로그램을 작성하시오.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

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

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

 

출력 조건

(1) 각 테스트 케이스마다 한 줄에 비대칭 타일링 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

 

 

입력 예제

3
2
4
92

 

출력 예제

0

2

913227494

 

 

 

 

3. 제약 조건

(1) 프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 한다.

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1): X

(2): 너비가 2 이하인 경우

 

 

 

 

6. 코드 및 풀이

: (1)과 (2) 두 개의 코드가 존재한다.

 

 

(1)는 전체 타일링 방법의 수에서 대칭인 타일링 방법 수를 빼는 것이다.

 

이때 2xN에 대해서 N을 기준으로 홀수일 때와 짝수일 때를 각각 계산한다.

 

만약 홀수라면, 아래의 그림처럼 중간에 1칸의 세로 타일이 있어야 한다.

* 단, 색칠된 왼쪽과 오른쪽의 타일링 방법은 대칭

만약 짝수라면, 아래의 그림처럼 중간에 2칸의 가로 타일과 절반을 나뉜 부분들이 서로 대칭 이어야 한다.

* 단, 색칠된 왼쪽과 오른쪽의 타일링 방법은 대칭

 

 

(1) 전체 타일링 방법의 수에서 대칭인 타일링 방법 수를 빼는 것

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

    private static int N;
    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];
            N = Integer.parseInt(sc.readLine());
            sb.append(solve(N)+"\n");
        }
        System.out.println(sb);
    }

    private static int solve(int width) {
        // 만약 홀수라면, (전체 타일링 방법의 수 - 대칭인 타일링 방법의 수)
        if(width%2==1) return (tiling(width) - tiling(width/2) + MOD) % MOD;


        // 만약 짝수라면, 
        //(전체 타일링 방법의 수 - (중간이 가로 2칸일 경우) - (중간 기준으로 왼쪽과 오른쪽 크기가 같은 경우))
        int ret = tiling(width);
        ret = (ret - tiling(width/2-1) + MOD) %MOD;	// 중간이 가로 2칸일 경우
        ret = (ret - tiling(width/2) + MOD) %MOD;	// 중간 기준으로 왼쪽과 오른쪽 크기가 같은 경우

        return ret;
    }

    private static int tiling(int width) {
        // 기저 사례(1): 더 이상 사각형을 쪼갤 수 없는 경우
        if(width<=1) return 1;

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

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

* 여기서 N이 짝수일 경우 MOD를 더하고 MOD로 %하는 것이 있는데, 이는 음수를 방지하기 위함이다.

* 예를 들어, 2xN를 채우는 방법의 수가 MOD+1가지 이고 2x(N/2)를 채우는 방법의 수가 100가지라면,

tiling(width) = 1이고 tiling(Width/2)=100일 테니 결과가 -99가 될 수 있다.

 

 

 

(2)는 직접 비대칭 타일링의 수를 세는 것이다.

 

단, 타일링 방법이 대칭인지 판단하기 위해서는 과거에 선택한 조각들에 대한 정보를 전부 재귀 호출을

해야하기 때문에 메모제이션은 불가능하다.

 

그러므로 맨 앞에서부터 타일링 방법을 만들어 가는 것이 아니라 양쪽 끝에서부터 동시에 만들어 나가는 것이다.

 

즉, 아래의 그림처럼 타일링 방법을 양쪽 끝을 덮은 타일들로 분류하는 것이다.

*(a)와 (b)는 양쪽 끝을 덮은 타일들이 서로 대칭이고, (c)와 (d)는 양쪽 끝을 덮은 타이들이 서로 비대칭이다.

 

(a)와 (b)는 가운데 회색 부분을 덮는 방법을 재귀 호출로 찾는데, 이 부분은 좌우 대칭이 아니어야 한다.

* 전체 타일링 방법이 대칭이 되기 때문이다.

 

(c)와 (d)는 가운데 남는 회색 부분을 덮는 방법을 찾는데, 이 부분은 대칭과 비대칭 둘 다 구해야 된다.

* 어짜피 양쪽이 비대칭이기 때문이다.

 

 

 

(2) 직접 비대칭 타일링의 수를 세는 것

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

    private static int N;
    private static int MOD = 1000000007;

    private static int[] cache1, cache2;

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

        for(int i=0; i<C; i++) {
            cache1 = new int[101];
            cache2 = new int[101];
            N = Integer.parseInt(sc.readLine());
            sb.append(solve(N)+"\n");
        }
        System.out.println(sb);
    }

    private static int solve(int width) {
        // 기저 사례(1): 너비가 2 이하인 경우
        if(width<=2) return 0;

        // 메모제이션
        if(cache2[width]!=0) return cache2[width];

        int ret=cache2[width];

        // 각각 그림 (a), (b), (c), (d)를 나타낸다.
        ret = solve(width-2) % MOD; 
        ret = (ret + solve(width-4)) % MOD;
        ret = (ret + tiling(width-3)) % MOD;
        ret = (ret + tiling(width-3)) % MOD;

        return ret;
    }

    private static int tiling(int width) {
        // 기저 사례(1): 더 이상 사각형을 쪼갤 수 없는 경우
        if(width<=1) return 1;

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

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

 

 

 

 

 

7.  점화식

- (1)과 (2) 둘 다 O(N)