13 X 13 으로 이루어진 정사각형을 작은 정사각형으로 채우기 위해 최소 필요한 사각형 갯수 문제

13 X 13으로 이루어진 정사각형이 있다. 이보다 작은 정사각형들로 가득 채우려면 최소 몇 개의 정사각형이 필요한지 계산해 내야 하는 문제다. 문제 설명을 세부적으로 풀어 쓴다면 13 곱하기 13 = 169 개의 칸수가 존재한다. 가장 작은 정사각형이 169개로 이루어져 13 X 13짜리 큰 정사각형 하나를 만들었다.

정사각형의 크기는 상관없이 13 X 13 문제 사각형보다 작은 "정사각형"으로 칸수를 다 채운다면 몇 개의 최소 사각이 필요하냐는 문제로 많이 채울 수 있는 큰 정사각형과 작은 사이즈를 활용해 가장 적은 수의 사각형으로 다 채워야 한다. 13짜리이기 때문에 궁극적으로 1X1짜리 가장 작은 정사각형이 출현할 수 밖에 없다.

결국 그런 작은걸 최소화 해서 전체 갯수를 줄이는게 문제 포인트, 사각형은 서로 겹칠 수 없다.

12X12를 채우게 되면 끝 가로줄과 끝 세로줄 전부 남는다. 정사각형으로만 채울 수 있기 때문에 결국에는 그 작은 칸을 하나씩 다 채울 수 밖에 없다. 25개 가장 작은 정사각형과 12짜리 정사각형 결국 26개로 채우는 모양이 되버림

타일러의 도전 12개 최소 값에 맞지 않아 땡. 모두 정사각형으로 채웠지만 갯수를 더 줄여야 함

그렇다. 한 칸짜리(1X1)가 크기는 작으면서 갯수는 한 자리를 차지하니 저걸 줄여야 한다.

3~9번 짜리를 어떻게 손질을 봐야 할 상황, 저런 정사각형은 자리만 차지하고 갯수만 늘림

모두 풀었지만 12개 타일러와 갯수는 같다. 풀다보면 12개에서 막힌다는 뜻이다.

나도 공감..이런 문제들은 먹거리를 크게 노리면 오히려 그게 함정인 경우가 많았음

큰 것으로 대충 땅을 먹고 중간 사이즈 2~3개 나머지는 소형 사이즈의 이런 패턴은 모두 12개로 종착지가 된다. 그렇담 대형이 아닌 중형 사이즈로 5~6개를 만들고 나머지는 소형으로 도전해야 하는 것도 다른 방법이 될수도...

뇌크러쉬의 도전. 정답은 아래부터 (답은 11개가 최소값)

한 칸짜리를 없앤다고 중형 사이즈로 채우려고 했는데 배치만 잘하면 11개가 가능

이것은 정답!! 11개의 정사각형으로 13 X 13 정사각형을 모두 채움!

타일러, 이장원의 12개 답과 배치도를 잘 보면 어디가 포인트 였는지 알 수 있다. 한 칸짜리!!

부동산 투자가나 건축가들이 해볼만한 문제, 자투리 땅 활용에는 이 문제만큼 재밌는것도 없으리 ㅋ