꾸준하게 거북이처럼

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이 n이 홀수일 때는 1x2, 2x1로 3xn 모양의 타일을 만들 수 없다. 짝수 일 때의 경우를 그려보면 위와 같은데, n이 4부터는 이전의 타일( d[2]와 d[2]를 가지고 만듦)을 이용해서 만드는 것뿐만 아니라 좀 새로운 모양의 타일이 2개씩 생긴다. n이 6일 때는 dp[4] * dp[2] + dp[2] * dp[4]의 새로운 모양타일 2개 + dp[6]에서 만들어진 새로운 모양 타일 2개 .... dp[i] = dp[i - 2] * 3 + dp[i - 4] * 2 + ..... + dp[0] * 2 와 같은 점화식을 구할 수 있다. 코드 dp = [0] * 3..