[동적 계획법] ASYMTILING 비대칭 타일링

#include <iostream>
#include <cstring>
 
const int MOD = 1000000007;
int wide = 0;
int cache[100][100][3];
 
int asy(int vertical, int horizontal, int before)
{
    int &ret = cache[vertical][horizontal][before], ishalf = 0, width = vertical+ indexx;
 
    if(ret != -1) return ret;
 
    if (wide % 2 == 0 && ((width == wide/2 + 1 && before == 2 )|| width == wide/2)) ishalf = -1;
    else if (wide%2 == 1 && width == wide/2) ishalf = -1;
 
    if(width >= wide-1) return  1 + ishalf;
 
    return ret = (asy(vertical, horizontal + 2, 2) +
                  asy(vertical + 1, horizontal, 1) + ishalf) % MOD;
}
 
int main(void)
{
    int testCase = 0;
 
    std::cin>>testCase;
 
    for(int i = 0; i < testCase; i++)
    {
        memset(cache, -1, sizeof cache);     
        std::cin>>wide;
        std::cout<<asy(0, wide, 0, 0)<<std::endl;
    }
}

1. 나의 문제 풀이

카운트를 직접 전부 세는 방법

 

카운트할 때 필요한 정보는

이전에 선택한 가로의 개수, 세로의 개수, 그리고 바로 이전단계의 종류이다.

 

대칭이 되는 경우는 총 4가지 가 있다.

1. 짝수 일때 가운데 부분이 가로 | 가로

2. 짝수 일때 가운데 부분이 세로 | 세로

3. 짝수 일때 가운데 부분이 가로 일때

4. 홀수 일때 가운데 부분이 세로 일때

 

그래서 만약 가운데 부분쪽을 카운트하고 있을 때 이에 해당하면 -1을 해준다.

 

그리고 세로를 선택하는 경우의 수와 가로를 선택하는 수를 다 더하여 리턴한다.

 

나의 풀이는 타일링 방법이 대칭인지 판단하기 위해 과거에 선택한 조각들에 대한 정보를

전부 재귀 호출에 전달하여 메모이제이션을 하고 있다. 이는 간결하지 못하며 좋지 않은 풀이이다. 

 

2. 책의 문제 풀이1: 단순화된 문제의 해법

 

책은 대칭인 타일링 방법의 수를 전체 타일링 방법의 수를 빼서 답을 얻어내는 코드를 구현하였다.

 

대칭 타일링 수를 세는 방법

1. n이 짝수인 경우와 홀수인 경우를 각각 나눠 보는 것.

2. n이 홀수인 경우, 타일링 방법이 대칭이기 위해서는 항상 정가운데, 왼쪽 오른쪽 서로 대칭.

3. n이 짝수인 경우, 정가운데 세로줄 둘을 가로타일로 덮고 나머지 절반이 대칭.

4. n이 짝수인 경우, 절반으로 나뉜 부분들이 서로 대칭인경우.

//2*width 크기의 사각형을 채우는 비대칭 방법의 수를 반환
int asymmetric(int width)
{
    if(width % 2 == 1)
 	return (tiling(width) - tiling(width/2) + MOD) % MOD;
    int ret = tiling(width);
    ret = (ret - tiling(width/2) + MOD) % MOD;
    ret = (ret - tiling(width/2-1) + MOD) % MOD;
    return ret;
}

뺄셈에서 뺀값이 음수일 수 있어서 MOD를 더하고 나머지를 구한다.

(ex. ret이 mod에 의해 나온 나머지 값이 더 작을 때)

 

함수 실행 자체는 상수시간이므로 이 문제의 시간 복잡도는 O(n)이 된다.

 

3. 책의 문제 풀이: 직접 비대칭 타일링의 수 세기

이 풀이는 내가 풀었던 방법이랑 유사하지만 양끝을 비교하면서 타일링의 수를 세어나간다.

 

비대칭 타일링 수를 세는 방법

1. 양끝이 같은 경우 가로 세로 각각 두개의 방법

    = 다음 부터 끝까지 1번이상이라도 2의 방법을 쓰면 비대칭이된다.

    = if (width <= 2) return 0;

    = 재귀호출로 해결

2. 양끝이 다른경우 가로 세로 각각 두개의 방법

    = 대칭이 될 수 없다.

    = 2번과 같이 tiling()로 해결

 

O(n)개의 입력에 대해 각각 상수시간으로 답을 계산하므로, 전체 시간 복잡도는 O(n).

 

int cache2[101];

int asymmetric2(int width)
{
    if(width < = 2) return 0;
    
    int& ret = cache2[width];
    if(ret != -1) return ret;
    
    ret = asymmetric2(width-2) % MOD;
    ret = (ret + asymmetric2(width - 4)) % MOD;
    ret = (ret + tiling(width-3)) % MOD;
    ret = (ret + tiling(width-3)) % MOD;
    return ret;
}

 

4. 다른 방법

 

피보나치 수열을 쓰는 풀이 방법

 

 

 

- 알고리즘 문제해결전략 261p

ASYMTILING