[BOJ] 2133 / 타일 채우기 / Python 파이썬

[BOJ] 2133 / 타일 채우기 / Python 파이썬

[BOJ] 2133 / 타일 채우기 / Python 파이썬

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

2133번: 타일 채우기

 

풀이

경우의 수를 구하고, 점화식을 찾아 풀어 보았다.

 

블럭 문제의 경우 N 과 N-1 사이의 관계가 명확한 경우의 문제가 많으므로 점화식을 이용하여 간단히 풀 수 있는 것같다.

 

N = 0 -> 1
N = 1 -> 0
N = 2 -> 3
N = 3 -> 0
N = 4 -> 11
N = 5 -> 0
N = 6 -> 41
N = 7 -> 0

 

1      3       11       41       ....
    2       8       30

2    = 1 * 2
8    = (3 + 1) * 2
30  = (11 + 3 + 1) * 2

 

홀수의 경우는 구할 수 없으므로, 짝수의 경우만 점화식이 구해 진다.

 

dp(N) = dp(N-2) + (dp(N-2) + .... + dp(0))*2

 

N = int(input())

dp = [0] * (N+2)
dp[0] = 1
dp[2] = 3

for i in range(4, N+1, 2):
    dp[i] = dp[i-2] + sum(dp[:i-1]) * 2
    
print(dp[N])