2133
BOJ 2133 타일 채우기
boj 2133 타일 채우기 n이 홀수일 때, 타일을 전부 채울 수 있는 방법은 없다. 그러므로 n이 짝수일 때만 살펴보면 된다. 테이블 D[i]를 n이 i일 때, 타일을 전부 채울 수 있는 방법 수라고 정의하자. 타일이 2칸일 때 채울 수 있는 방법의 수가 3가지인 것은 쉽게 알 수 있다. 그리고 힌트를 보면 4칸의 경우 2칸인 경우를 이용하지 않고 채우는 방법이 2가지가 있다는 것을 알 수 있다. 이 사실만으로 간단하게 점화식을 D[i] = D[i-2]x3 + D[i-4]x2 라고 하면 틀린다. 위의 사진을 보면, 타일이 2칸씩 늘어날 때마다 채우는 방식 2가지가 추가된다. 이를 바탕으로 점화식을 구현해보자. D[i] = D[i-2]x3 + D[i-4]x2 + D[i-6]x2 + ... + D[0]x..