타일 채우기 풀이

문제 링크: https://www.acmicpc.net/problem/2133

백준  알고리즘 기초 1/2 401에서 12번째 - 2133번 타일 채우기를 풀어보았다.

 

풀이: 기존의 타일링 문제를 참고해서 풀려고 했지만, 점화식 찾기가 어려워서 검색해 가면서 찾았다.

 

C++

 

Python

n=int(input())
dp=[0 for i in range(31)]
dp[2]=3
for i in range(3,n+1):
	if i%2==0: dp[i]=3*dp[i-2]+2*sum(dp[:i-2])+2
print(dp[n])

Java