[백준] 2133 - 타일 채우기 [Python(파이썬)]

문제

www.acmicpc.net/problem/2133

2133번: 타일 채우기

풀이

아래의 그림을 통해 점화식을 간단하게 표현할 수 있다.

f(n)은 n만큼의 너비를 지니는 타일을 채우는 경우의 수이며 g(n)은 f(n)에서 1x1만큼의 타일을 빼고 채우는 경우의 수다. 

 

f(n)는 n이 홀수일 때 f(n) = 0이 되고, g(n)은 n이 짝수일 때 g(n) = 0이 된다.

이를 고려하여 base case를 처리한다.

 

코드

def solve(n):
    if n % 2 != 0:
        return 0
    for i in range(2, n+1, 2):
        f[i] = f[i-2] + 2*g[i-1] 
        for j in range(i+1, n, 2):
            g[j] = f[j-1] + g[j-2]
    return f[n]

n = int(input())
f = [0 for _ in range(31)]
g = f[:]
f[0], g[1] = 1, 1

print(solve(n))