[백준 14601] 분할 정복

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

 

한 변의 길이가 $n$인 정사각형 3개로 만든 ㄱ자 타일을 길이가 $n$인 ㄱ자 타일이라고 정의하자.

길이가 2인 ㄱ자 타일은 길이가 1인 ㄱ자 타일로 아래 그림과 같이 만들 수 있다. 

 

 

같은 방법으로 길이가 2인 ㄱ자 타일로 길이가 4인 ㄱ자 타일을 만들 수 있고 길이가 $2^{n-1}$인 ㄱ자 타일로 길이가 $2^n$인 ㄱ자 타일로 만들 수 있다.

 

따라서 전체 정사각형 타일을 사분면으로 나눈 뒤 배수구가 어느 사분면에 위치해 있는지 파악하고, 배수구가 없는 사분면은 분할정복으로 ㄱ자 타일을 배치하는 과정을 반복하면 된다.