[BOJ]2133. 타일 채우기

문제:

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

입력:

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

출력:

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

풀이방법:

홀수인 경우는 만들 수 없으니 제외를 하고 각 n은 이전 값의 3배에다가 더 이전의 값들의 2배씩을 더한 값들이다.

n=int(input())
d=[0]*(n+1)
d[0]=1
for i in range(2,n+1,2):
    d[i]=d[i-2]*3
    for j in range(i-4,-1,-2):
        d[i] +=d[j]*2
print(d[n])

문제링크:

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