타일 3 x n

[baekjoon 2133] 타일 채우기- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 일반적인 타일 문제라 생각했지만 추가적인 아이디어가 필요한 문제였다. 3 X N의 벽을 2X1, 1X2로 채워야 한다. 또한 벽의 높이가 3이기 때문에 직접 찾아보면 N이 홀수이면 채울 수가 없다. 그러면 N이 짝수일 때 고려를 해보면 N = 2 일 때 이 세가지 케이스가 등장한다. 가로 두 칸을 차지하는 이 블록 3개는 우리가 기본 타일 채우기 문제를 풀듯이 계속 사용된다. N = 4 일 때 이 세 가지 블록이 기존 타일을 채우던 것처럼 너비 2개씩 차지하면서 구성하는 경우의 수는 DP [2] * 3이다. 그러나 4가지..