문제

• 백준-2133 : 타일 채우기
• 문제링크

풀이

1. 처음에 아무 타일도 놓지 않는 경우의 수를 0으로 생각해서 계속 틀렸다.
2. 길이 1인 경우의 수도 0으로 명시해줘야 한다.

leng = int(input())

memo = [0]*(leng+1)
memo[0:3] = [1,0,3]

summemo = 0
for i in range(4, leng+1):
    if i%2 ==0:
        summemo += memo[i-4]
        memo[i] = 3*memo[i-2]+ 2*summemo

print(memo[leng])