작은 정사각형을 사용하여 큰 사각형을 구성하십시오.

Question

나는 큰 정사각형의 사각형을 가지고 있습니다. N. 이 큰 사각형을 구성하는 데 필요한 작은 사각형 수를 계산하려면 1에서 N-1까지의 가장자리 값을 가진 작은 사각형을 사용하십시오. 작은 사각형을 무제한으로 사용할 수 있습니다. 유일한 제한은 minimum 개의 작은 사각형을 사용해야한다는 것입니다. 예를 들어, N = 3 인 경우 크기가 1 인 5 개의 정사각형과 1 크기의 사각형을 사용하여이 사각형을 구성 할 수 있습니다 2 . 주어진 값 N에 대해이 문제를 어떻게 해결할 수 있습니까?

Answer 1

심지어 N의 경우, 가능한 한 최소한 N/2 인 4 개의 정사각형을 사용할 수 있습니다. 홀수가 N 인 경우 조금 더 복잡합니다. 홀수 N에 대한 가능한 해결책 중 하나는 (N+1)/2의 1 제곱이고 (N-1)/23 및 N-1의 크기는 1이지만 전체가 확실하지는 않습니다 ... 예를 들어 N=9 인 경우 12 개의 사각형이 제공되는데 더 좋은 해결책 3 개의 3x3 사각형이 존재합니다. 그래도 N 프라임을위한 최상의 솔루션 일 수 있습니다.