[BOJ 14601] 샤워실 바닥 깔기 (Large)

https://www.acmicpc.net/problem/14601

14601번: 샤워실 바닥 깔기 (Large)

 

 

이 문제는 정사각형 타일 하나를 뺀 2^k × 2^k 정사각형 판을 L-트로미노를 이용해 채우는 문제입니다. 정사각형 타일 하나를 뺀 2^k × 2^k 정사각형 판을 L-트로미노를 통해 채울 수 있다는 것은 수학적 귀납법을 이용해 간단하게 증명할 수 있습니다. 

 

k가 1인 경우에는 아래와 같이 어떠한 경우에도 가능하다는 것이 자명합니다.

 

k가 1인 경우에 타일을 채우는 방법

 

이제 (정사각형 타일 하나를 뺀) 2^k-1 × 2^k-1 판을 L-트로미노로 채울 수 있을 때 2^k × 2^k 판을 채울 수 있음을 증명하면, 이 문제에 대한 접근법을 얻을 수 있습니다. 먼저 2^k × 2^k 정사각형 판을 4개의 2^k-1 × 2^k-1 정사각형 판으로 나누면, 꽉 채워진 2^k-1 × 2^k-1 판 3개와 정사각형 타일 하나가 빠진 2^k-1 × 2^k-1 판 하나를 얻을 수 있습니다. 이때 꽉 채워진 2^k-1 × 2^k-1 판 3개에 대해 중앙에 가장 가까운 가장자리 타일을 하나씩 골라 L-트로미노를 배치할 수 있고, 이 부분을 제외하면 꽉 채워진 2^k-1 × 2^k-1 판 3개가 각각 정사각형 타일 하나가 빠진 판이 됩니다. 이러한 방식으로 접근하면 2^k × 2^k 판을 채우는 문제를 2^k-1 × 2^k-1 판 4개를 채우는 문제로 나눌 수 있습니다.

 

임의의 k에 대해 2^k × 2^k  정사각형 판을 채우는 방법

 

따라서, 주어진 판을 같은 크기의 4개의 판으로 나누고, 중앙에 있는 L-트로미노의 배치를 결정하는 과정을 반복하면 2^k × 2^k 판을 채울 수 있는 L-트로미노의 배치를 얻을 수 있습니다.