태그 : 분할정복 https://www.acmicpc.net/problem/14601 14601번: 샤워실 바닥 깔기 (Large) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net 처음에는 k의 크기가 large문제임에도 7인걸로 보아서 3개를 깔을수있는 완전탐색 분기를 어떻게하면 효율적으로 짤까 생각했었다. 완탐이 아직 부족한가보다 하고 이 문제를 쳐보니까 이산수학, 그 중에서도 수학적 귀납법 으로 증명할 수 있는 트로미노 타일링이라는 유명한 문제였고, 이 문제에서 요구하는 타일을 전부 칠하는 과정 또..