타일 채우기

bookmark

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

모범답안

n = int(input())
MAX = 31
dp = [0] * MAX
dp[2] = 3
dp[4] = 11
for i in range(6, MAX, 2):
    dp[i] = dp[i - 2] * 4 - dp[i - 4]


print(dp[n])

모범답안 2

N = int(input())

d = [0]*31
d[0] = 1

for i in range(2, N+1, 2):
    d[i] = d[i-2] * 3
    for j in range(0, i-2, 2):
        d[i] += d[j] * 2

print(d[N])

점화 식을 세워서 작성