[종만북] 비대칭 타일링(ASYMTILING) (python)

문제 출처 :

www.algospot.com/judge/problem/read/ASYMTILING

algospot.com :: ASYMTILING

문제 풀이 :

jinu0418.tistory.com/37 

[종만북] 타일링(TILING2) (Python)

• 위의 문제에서 조금 더 나아간 문제이다.
• 간단하게 양옆이 대칭인 부분에 대해서 빼면 된다. 때문에 위에서 구한 전체 경우의 수에서 대칭인 경우만 빼주면 된다.
• 대칭인 부분은 다음 그림과 같이 3가지로 나눠진다.

대칭을 이루는 타일의 종류

• 때문에 타일링 문제에서 사용한 solve 함수에 대칭을 이루는 타일 종류를 빼는 symm함수를 구현하여 문제를 해결하였다.
• 이때 초기값 dp[2]에 대해서 문제가 있었는데 이경우는 예외처리를 통해서 해결하였다.

dp = [-1]*101
mod = 1000000007
c = int(input())

def init_():
    global dp
    dp = [-1]*101

    dp[0]=0
    dp[1]=1
    dp[2]=2
    dp[3]=3
    dp[4]=5


def solve(N):
    global dp

    if(dp[N]!=-1):
        return dp[N]%mod

    dp[N] = (solve(N-1)%mod+solve(N-2)%mod)%mod

    return dp[N]

def symm(N):
    global dp
    ret = solve(N)

    if((N-1)%2==0):
        ret = (ret- solve((N-1)//2) +mod )%mod
    if((N-2)%2==0):
        ret = (ret - solve((N-2)//2) + mod)%mod
    if(N%2==0):
        ret = (ret - solve(N//2) +mod)%mod

    return ret



for _ in range(c):
    init_()
    n = int(input())
    if(n==2):
        print(0)
    else:
        print(symm(n))