코딩 연습

프로젝트 오일러 126번 본문

project euler with python

프로젝트 오일러 126번

코딩아저씨 2016. 3. 15. 15:58
반응형

The minimum number of cubes to cover every visible face on a cuboid measuring 3×2×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×1×1 also requires twenty-two cubes; similarly the first layer on cuboids measuring 5×3×1,7×2×1, and 11×1×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×2×1) 직육면체를 다 가리기 위해서 필요한 길이 1인 정육면체의 최소 개수는 위 그림 처럼 22개다. 이것을 첫 번째 막을 쳤다고 하자.

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

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

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

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

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


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

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

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

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

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

따라서 이 모두를 더해주면 

2xy+4x+4y+2×k=1n2(4k+4(n1)+2x+2y)+2xz+2yz+4z(n1)

=2(xy+yz+zx)+4(n1)(x+y+z+n2) 가 된다.

따라서 nthlayer(n,x,y,z)=2(xy+yz+zx)+4(n1)(x+y+z+n2) 이다.

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

이제 n,x,y,z 를 어떤 범위에서 변화시켜 가면서 함숫값을 계산할 것인가를 고민해야 한다. 중복을 피하기 위해서 xyz 인 경우만을 다룰 것이고, 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 보다 작거나 같고 xyz 를 만족하는 범위에서 x,y,z,n 값들을 하나씩 증가시켰다. 그리고 동일한 함숫값이 나올 때마다 count[함숫값] 을 1씩 증가시켰다. 

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

반응형

'project euler with python' 카테고리의 다른 글

프로젝트 오일러 128번  (0) 2016.03.15
프로젝트 오일러 127번  (0) 2016.03.15
프로젝트 오일러 125번  (0) 2016.03.15
프로젝트 오일러 124번  (0) 2016.03.15
프로젝트 오일러 123번  (0) 2016.03.15