[Python] 1793 타일링 DP

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

1793번: 타일링

 

 

풀이

 

N번째 타일을 채우는 방법 = N-1 타일에 1*2 타일 추가 + N-2 타일에 2*2 타일을 추가하는 방법이다.

N-1번째 타일에 1칸을 추가하면 1*2 타일을 붙이는 방법 밖에는 없다.

그리고 N-2번째 타일에서 2*2 타일을 붙이는 방법은 3가지이지만  || 모양으로 붙이는 방법은 (N-1에 1*2 추가하기)와 겹치므로 N-2번째 타일에 ㅁ, = 모양을 추가하는 방법 수를 더하면된다.

그래서 점화식은

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

가 된다.

def DP(n):
    if n == 0 or n == 1 : return 1
    memo = [0 for _ in range(n+1)]
    memo[0], memo[1] = 1, 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + (memo[i-2] * 2)
    return memo[n]

try : 
    while True:
        print(DP(int(input())))
except:
    pass