A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest "straight line" distance from S to F is 10 and the path is shown on the diagram.
However, there are up to three "shortest" path candidates for any given cuboid and the shortest route doesn't always have integer length.
It can be shown that there are exactly 2060 distinct cuboids, ignoring rotations, with integer dimensions, up to a maximum size of M by M by M, for which the shortest route has integer length when M = 100. This is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions when M = 99 is 1975.
Find the least value of M such that the number of solutions first exceeds one million.
S라는 거미가 가로 6, 세로 5, 높이 3인 육면체 방의 구석에 있고, 반대쪽 코너에는 파리 F가 있다. 방 표면을 따라 S에서 F로 가는 가장 짧은 "직선" 거리는 10이고, 경로는 다음 그림과 같다.
그러나, 육면체 방에서는 3개의 최단 경로 후보가 있으며, 최단 경로는 정수길이가 아닐 수 있다.
회전을 무시하고, M=100일때 최대 가로 M(이하), 세로 M(이하), 높이 M(이하)이고 최단 경로가 정수인 육면체는 2060개가 있다. 이것은 M이 99일 때, 최단 경로가 정수인 육면체는 1975개 이며, 100일 때 처음으로 육면체의 수가 2천을 넘는다.
최단 경로가 정수인 육면체의 숫자가 1백만을 넘는 첫 M을 구하시오.
--------------------------------------------------------------------------
문제에서 회전을 무시한다고 했으므로, 경우의 수를 줄여서 계산해야 한다.
육면체에서 면의 길이 순서대로 a, b, c라고 한다면, 1<=a<=b<=c<=M이 된다. 이 조건에서, c**2+(a+b)**2의 제곱근이 자연수인 경우를 찾으면 된다.
a, b, c에 대한 3번의 반복문이 있어 실행시간이 필요하지만, 반복문을 구성할 때 위 조건에 따라 잘 정리한다면(b는 a값부터 반복문을 시작하고, a, b의 최대값은 c) 그렇게 어렵지 않게 구현 가능하다.