[Python] 2133 타일 채우기

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

풀이

https://lyzqm.blogspot.com/2017/04/2133.html

2133 타일 채우기

위에 블로그를 참고했다.

마지막이 될 수 있는 유형은 이 세가지 이다

 

 

 

1,2번은 2가지 유형으로 만들어질 수 있으므로

 

 

점화식은 아래처럼 된다.

 

        memo[i][0] = memo[i-2][0]*2 + memo[i-2][1] + memo[i-2][2]

        memo[i][1] = memo[i-2][1] + memo[i-2][1]*2 + memo[i-2][2]

        memo[i][2] = memo[i-2][0] + memo[i-2][1] + memo[i-2][2]

 

 

N = int(input())

if N % 2 == 1 :
    print(0)
else :
    memo = [[0,0,0] for _ in range(N+1)]
    memo[2][0] = memo[2][1] = memo[2][2] = 1

    for i in range(4,N+1,2):
N = int(input())

if N % 2 == 1 :
    print(0)
else :
    memo = [[0,0,0] for _ in range(N+1)]
    memo[2][0] = memo[2][1] = memo[2][2] = 1

    for i in range(4,N+1,2):
        memo[i][0] = memo[i-2][0]*2 + memo[i-2][1] + memo[i-2][2]
        memo[i][1] = memo[i-2][1] + memo[i-2][1]*2 + memo[i-2][2]
        memo[i][2] = memo[i-2][0] + memo[i-2][1] + memo[i-2][2]

    print(memo[N][0] + memo[N][1] + memo[N][2])



    print(memo[N][0] + memo[N][1] + memo[N][2])