프로젝트 오일러 126번

The minimum number of cubes to cover every visible face on a cuboid measuring \(3 \times 2 \times 1\) is twenty-two.

If we then add a second layer to this solid it would require forty-six cubes to cover every visible face, the third layer would require seventy-eight cubes, and the fourth layer would require one hundred and eighteen cubes to cover every visible face.

However, the first layer on a cuboid measuring \(5 \times 1\times 1\) also requires twenty-two cubes; similarly the first layer on cuboids measuring \(5 \times 3 \times 1, \; 7 \times 2 \times 1,\) and \(11\times 1 \times 1\) all contain forty-six cubes.

We shall define \(C(n)\) to represent the number of cuboids that contain \(n\) cubes in one of its layers. So \(C(22)=2, \; C(46)=4, \; C(78)=5,\) and \(C(118)=8\).

It turns out that \(154\) is the least value of \(n\) for which \(C(n)=10\).

Find the least value of \(n\) for which \(C(n)=1000\). 

---

크기가 가로 \(3\), 세로 \(2\), 높이 \(1\)인 (\(3 \times 2 \times 1\)) 직육면체를 다 가리기 위해서 필요한 길이 \(1\)인 정육면체의 최소 개수는 위 그림 처럼 \(22\)개다. 이것을 첫 번째 막을 쳤다고 하자.

이렇게 해서 얻은 입체를 다시 다 가리기 위해서는 (즉, 두 번째 막을 치기 위해서는) 최소 \(46\)개의 정육면체가 필요하다. 두 번째 막을 쳐서 얻은 입체에 다시 세 번째 막을 치기 위해서는 최소 \(78\)개의 정육면체가 필요하고, 같은 방식으로 네 번째 막을 치기 위해서는 최소 \(118\)개의 정육면체가 필요하다.

만약 크기가 \(5 \times 1 \times 1\) 인 직육면체에 첫 번째 막을 치기 위해서는 이 역시 최소 \(22\)개의 정육면체가 필요함을 알 수 있고, 비슷하게 크기가 \(5 \times 3 \times 1, \; 7 \times 2 \times 1, \; 11 \times 1 \times 1\) 인 직육면체들에 첫 번째 막을 치기 위해서는 최소 \(46\)개의 직육면체가 필요하다.

\(C(n)\) 은 몇 번째가 막이 되었든 그 막을 치기 위해 필요한 정육면체의 최소 개수가 \(n\) 개가 되는 직육면체의 개수라고 정의하자. 예를 들어, \(C(22)=2, \; C(46)=4, C(78)=5\), 그리고 \(C(118)=8\) 이 된다.

또한 \(C(n)=10\) 이 되는 최소의 자연수 \(n\) 은 \(154\) 라는 것이 알려져 있다.

그렇다면 \(C(n)=1000\) 이 되는 최소의 자연수는 무엇일까?     

먼저 크기가 \( x \times y \times z\) 인 직육면체에 \(n\) 번째 막을 치기 위해 필요한 정육면체의 개수를 나타내는 함수를 nthlayer(n, x, y, z) 라고 하자.

이 함수를 구하기 위해 우리는 \(n\) 번째 막을 치고 난 후 생기는 입체를 층으로 나누어 생각해 보자. 

이런식으로 생각한다면 지상 \(k\)층과 지하 \(k\) 층(\(-k\)층)을 가리기 위해서는 같은 개수의 정육면체가 필요하므로 지상 \(k\)층에 대해서만 생각하고 \(2\)배를 해 주면 된다. 

자 그렇다면 크기 \(x \times y \times z\) 인 직육면체를 시작으로 \(n\) 번째 막을 치기 위해 필요한 정육면체의 개수를 계산해 보자.

먼저 지상 \(n\) 층에서는 \(x \times y\) 의 정육면체가 필요하고, 지상 \(n-1\) 층에는 \(2x + 2y\) 개의 정육면체가 필요하다. 또한 지상 \(k\) 층에는 (단, \(k=1, \;2,\; \cdots,\; n-2\))  \(2x + 2y\) 개의 정육면체와 더불어 그 사이사이를 메꿔줄 \(4 \times -k-n-1\) 개의 정육면체가 필요하다. 즉, \(2x+2y+4(-k+n-1)\) 개의 정육면체가 필요하다. 또한 0층에는 \( 2xz + 2yz\) 와 더불어 그 사이사이를 메꿔줄 \(4 \times z \times (n-1)\) 개의 정육면체가 필요하다.

따라서 이 모두를 더해주면 

\(2xy +4x + 4y + 2 \times \sum \limits_{k=1}^{n-2} (-4k+4(n-1)+2x+2y) + 2xz + 2yz + 4z(n-1)\)

\(= 2(xy+yz+zx) + 4(n-1)(x+y+z+n-2)\) 가 된다.

따라서 \({\rm nthlayer}(n, x, y, z) = 2(xy+yz+zx)+4(n-1)(x+y+z+n-2)\) 이다.

(이 함수식을 구해내기가 만만치 않지만, 그림을 그려가면서 하나씩 차근차근 생각해보면 충분히 함수식을 얻어낼 수 있을 것이다. 그림 그리는 것을 두려워하지 말자!!)

이제 \(n,\; x, \; y, \; z\) 를 어떤 범위에서 변화시켜 가면서 함숫값을 계산할 것인가를 고민해야 한다. 중복을 피하기 위해서 \(x \ge y \ge z\) 인 경우만을 다룰 것이고, \(x, \; y, \; z\) 값 자체에 제한을 두는 것 보다는 함숫값에 제한을 두는 방법이 더 효과적임을 시행착오를 거쳐 알 수 있었다. 다음 파이썬 코드를 보자.

limit = 20000
count = [0] * (limit + 1)
z = 1
while nthlayer(1, z, z, z) <= limit:
    y = z
    while nthlayer(1, z, y, z) <= limit:
        x = y
        while nthlayer(1, x, y, z) <= limit:
            n = 1
            while nthlayer(n, x, y, z) <= limit:
                count[nthlayer(n, x, y, z)] += 1
                n += 1
            x += 1
        y += 1
    z += 1

일단 함수 nthlayer 의 제한을 \(20000\) 으로 했다. 이 값도 시행착오를 거쳐 찾을 수 있었다. 그리고 nathlayer 의 값이 \(20000\) 보다 작거나 같고 \(x \ge y \ge z\) 를 만족하는 범위에서 \(x, \; y, \; z, \; n\) 값들을 하나씩 증가시켰다. 그리고 동일한 함숫값이 나올 때마다 count[함숫값] 을 \(1\)씩 증가시켰다. 

결국 리스트 count에서 그 값이 \(1000\)인 것들의 index 중 가장 작은 것이 우리가 찾는 답이 된다.