DP - 타일링 문제 1,2,3

    // 2×n 직사각형을 1×2, 2×1 타일로 채우는 방법의 수
    // 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
    int tile1(int n) {
        int a = 1;
        int b = 2;

        if (n == 1) {
            return a;
        } else if (n == 2) {
            return b;
        }

        int result = 0;

        for (int i = 2; i < n; i++) {
            result = a + b;
            a = b;
            b = result;
        }

        return result % 10007;
    }

    // 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수
    // 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
    int tile2(int n) {
        int a = 1;
        int b = 3;

        if (n == 1) {
            return a;
        } else if (n == 2) {
            return b;
        }

        int result = 0;

        for (int i = 2; i < n; i++) {
            result = a*2 + b;
            a = b;
            b = result;
        }

        return result % 10007;
    }
    
//3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수
int tile3(int n) {
        if(n == 0) return 1;
        if(n == 1) return 0;
        if(n == 2) return 3;

        if (arr[n] != 0) {
            return arr[n];
        }
        arr[n] = tile3(n - 2) * 3;

        for (int i = 3; i <= n; i++) {
            if (i % 2 == 0) {
                arr[n] += 2 * tile3(n - i);
            }
        }

        return arr[n];
    }