반응형 샤워실 바닥깔기 썸네일형 리스트형 [분할 정복] L-트로미노(L-Tromino) 타일링 1. 트로미노란? 트로미노(Tromino)란, n=3인 폴리오미노(polyomino)로, 크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형이다. 따라서 다음과 같이 두 개의 트로미노가 존재할 수 있다. 2. $2^n$ x $2^n$ L-트로미노 타일링 이제, 이 트로미노중에서 일자형이 아닌 L 모양의 트로미노를 한 변의 길이가 $2^n$인 정사각형에 배치하는 것이 목표이다. 결론부터 말하자면, L-트로미노는 1x1 한 칸을 제외하고, 한 변의 길이가 $2^n$인 정사각형을 항상 채울 수 있다. 증명은 다음과 같이 수학적 귀납법으로 가능하다. [정리] $2^n$ X $2^n$ 크기의 정사각형에 1x1 한 칸을 제외하고 항상 L-트로미노로 모두 채울 수 있다. [증명] 1. n = 1일 때 n = 1인 .. 이전 1 다음
