일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 코틀린 시작하기
- Big-Oh notation
- 빅오 표기법
- linear dependence
- nonhomogeneous linear system
- homogeneous linear system
- nontrivial solution
- 빅세타
- 배열 섞기
- NumPy
- Big Omega
- itertools
- 빅오메가
- trivial solution
- python
- 일차변환
- 알고리즘 분석의 실례
- 이진 탐색
- 재귀함수
- matrix-vector product
- Big Theta
- Big-Oh 예제
- one-to-one
- 랜덤 순서 배열
- recursive algorithms
- matrix fo a linear transformation
- matrix trnasformations
- Big-O 예제
- 코틀린 Hello World!
- solutions of matrix equation
- Today
- Total
코딩 연습
프로젝트 오일러 126번 본문
The minimum number of cubes to cover every visible face on a cuboid measuring 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 also requires twenty-two cubes; similarly the first layer on cuboids measuring and all contain forty-six cubes.
We shall define to represent the number of cuboids that contain cubes in one of its layers. So and .
It turns out that is the least value of for which .
Find the least value of for which .
크기가 가로 , 세로 , 높이 인 () 직육면체를 다 가리기 위해서 필요한 길이 인 정육면체의 최소 개수는 위 그림 처럼 개다. 이것을 첫 번째 막을 쳤다고 하자.
이렇게 해서 얻은 입체를 다시 다 가리기 위해서는 (즉, 두 번째 막을 치기 위해서는) 최소 개의 정육면체가 필요하다. 두 번째 막을 쳐서 얻은 입체에 다시 세 번째 막을 치기 위해서는 최소 개의 정육면체가 필요하고, 같은 방식으로 네 번째 막을 치기 위해서는 최소 개의 정육면체가 필요하다.
만약 크기가 인 직육면체에 첫 번째 막을 치기 위해서는 이 역시 최소 개의 정육면체가 필요함을 알 수 있고, 비슷하게 크기가 인 직육면체들에 첫 번째 막을 치기 위해서는 최소 개의 직육면체가 필요하다.
은 몇 번째가 막이 되었든 그 막을 치기 위해 필요한 정육면체의 최소 개수가 개가 되는 직육면체의 개수라고 정의하자. 예를 들어, , 그리고 이 된다.
또한 이 되는 최소의 자연수 은 라는 것이 알려져 있다.
그렇다면 이 되는 최소의 자연수는 무엇일까?
먼저 크기가 인 직육면체에 번째 막을 치기 위해 필요한 정육면체의 개수를 나타내는 함수를 nthlayer(n, x, y, z) 라고 하자.
이 함수를 구하기 위해 우리는 번째 막을 치고 난 후 생기는 입체를 층으로 나누어 생각해 보자.
이런식으로 생각한다면 지상 층과 지하 층(층)을 가리기 위해서는 같은 개수의 정육면체가 필요하므로 지상 층에 대해서만 생각하고 배를 해 주면 된다.
자 그렇다면 크기 인 직육면체를 시작으로 번째 막을 치기 위해 필요한 정육면체의 개수를 계산해 보자.
먼저 지상 층에서는 의 정육면체가 필요하고, 지상 층에는 개의 정육면체가 필요하다. 또한 지상 층에는 (단, ) 개의 정육면체와 더불어 그 사이사이를 메꿔줄 개의 정육면체가 필요하다. 즉, 개의 정육면체가 필요하다. 또한 0층에는 와 더불어 그 사이사이를 메꿔줄 개의 정육면체가 필요하다.
따라서 이 모두를 더해주면
가 된다.
따라서 이다.
(이 함수식을 구해내기가 만만치 않지만, 그림을 그려가면서 하나씩 차근차근 생각해보면 충분히 함수식을 얻어낼 수 있을 것이다. 그림 그리는 것을 두려워하지 말자!!)
이제 를 어떤 범위에서 변화시켜 가면서 함숫값을 계산할 것인가를 고민해야 한다. 중복을 피하기 위해서 인 경우만을 다룰 것이고, 값 자체에 제한을 두는 것 보다는 함숫값에 제한을 두는 방법이 더 효과적임을 시행착오를 거쳐 알 수 있었다. 다음 파이썬 코드를 보자.
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 의 제한을 으로 했다. 이 값도 시행착오를 거쳐 찾을 수 있었다. 그리고 nathlayer 의 값이 보다 작거나 같고 를 만족하는 범위에서 값들을 하나씩 증가시켰다. 그리고 동일한 함숫값이 나올 때마다 count[함숫값] 을 씩 증가시켰다.
결국 리스트 count에서 그 값이 인 것들의 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 |