링크 www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이 3XN 크기의 벽을 2X1, 1X2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 일단 힌트를 가지고 N이 작은 경우를 나열해보면 아래와 같다. 접근하기 DP[N]을 3XN의 타일을 채우는 경우의 수라고 두자. 3X1과 3X3은 2X1, 1X2 크기의 타일로 채울 수 있는 경우가 없다. 즉, 3XN에서 N이 홀수일 때는 경우의 수가 0이 된다는 것이다. 그럼 N이 짝수일 때를 생각해보면, 3X2 크기를 채울 수 있는 방법이 3개가 있다. 3X4를 채울 수 있는 방법은 3X2 크기를 채운 경우의 수에 남은 ..
