책 이야기

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

변의 길이가 정수이고 정수 크기의 면적을 가지는 정삼각형이 없다는 것은 증명하기 쉽다. 그러나, 거의 정삼각형인 5-5-6의 면적은 12로 정수가 된다.

두 변이 같고 다른 변과 길이 차이가 1 이하인 삼각형을 "거의 정삼각형"으로 정의하고자 한다.

변의 길이와 면적이 정수이고 둘라가 10억을 이하인 모든 "거의 정삼각형"의 둘래의 합계를 구하시오.

--------------------------------------------------------------------------

"거의 정삼각형"을 다시 생각해보면 2개의 직각삼각형이 붙어 있는 구조이며, 직각삼각형의 빗변(가장 긴 변)이 "거의 정삼각형"에서 길이가 같은 변이 된다. 그리고 길이가 같은 변을 a, 나머지 변을 b라 하면, 문제에서 정의한 내용에 따라 b=a±1이 되고, "거의 정삼각형" 안에 있는 직각삼각형은 빗변이 a, 다른 변은 피타고라스 정리에 의해 각각 b/2=(a±1)/2, (a**2-(b/2)**2)**0.5가 된다.

문제에서 둘레와 면적이 모두 정수가 된다고 했으므로 b, b/2, (a**2-(b/2)**2)**0.5 모두 정수가 되어야 하며 a*2+b는 10억 이하가 되어야 한다. 그리고, b/2가 정수가 되기 위해서는 a는 홀수가 된다.

이런 전제조건에 따라 a가 커지면서 b, b/2, (a**2-(b/2)**2)**0.5가 정수이고, 둘레가 10억 이하인 "거의 정삼각형"을 계속 구했는데, 정상적으로 나와야 할 갯수보다 6개가 더 나와서 둘레의 합이 훨씬 크게 나오는 문제가 생겼다.

원인을 파악해 보니 (a**2-(b/2)**2)**0.5 값을 int(a**2-(b/2)**2)**0.5)와 비교해서 같으면 정수로 판별했는데, 제곱수와 차이가 매우 미세하면 제곱수가 아닌데도 두 값이 같게 나오는 문제 때문에 답을 6개나 더 구한 것으로 추정되었다.

is_integer() 등 몇 가지 방법을 적용했지만 해결되지 않아서, 제곱근을 씌운 상태에서 계산하지 않고 제곱인 상태에서 값을 비교해서 제곱수 여부를 판별하게 했더니 정답을 구할 수 있었다. 이전 문제에서 비슷한 경험이 있어 빨리 해결 가능했지, 로직의 문제가 아닌 프로그램 고유 특성에서 생기는 이런 현상은 찾기가 쉽지 않은 것 같다.

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) 그렇게 어렵지 않게 구현 가능하다.

The points P (x1, y1) and Q (x2, y2) are plotted at integer co-ordinates and are joined to the origin, O(0,0), to form ΔOPQ.

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is,
0 ≤ x1, y1, x2, y2 ≤ 2.

Given that 0 ≤ x1, y1, x2, y2 ≤ 50, how many right triangles can be formed?

좌표 P (x1, y1)과 Q (x2, y2)은 정수 좌표에 있으며, 시작점인 O(0, 0)과 연결되어 삼각형 ΔOPQ를 만든다.

좌표가 0과 2 사이일 때, 정확히 14개의 직각삼각형을 구할 수 있다.

0 ≤ x1, y1, x2, y2 ≤ 2.

0과 50 사이(0 ≤ x1, y1, x2, y2 ≤ 50)일 때 몇 개의 직각삼각형이 있는가?

--------------------------------------------------------------------------

O, P, Q 간의 관계를 잘 설정하면 반복문을 통해 만들어지는 삼각형을 피타고라스 정리(a²+b²=c²)를 이용해 직각삼각형인지 판단하면 되는 문제로 파악되었다.

O를 기준으로 P는 오른쪽, Q는 위쪽에 있는 좌표로 계산하기로 설정하였고, 반복문을 통해 P, Q가 가능한 모든 좌표에 대해 OP, OQ, PQ 거리를 구해서 피타고라스 정리를 만족하는 삼각형의 갯수를 구하였다.

P, Q의 한계를 조금 더 세밀하게 설정하면 속도가 더 빨라질 것 같았지만, 크게 늦지 않게 답을 구할 수 있어 만족하기로 했다.

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

    12 cm: (3,4,5)
    24 cm: (6,8,10)
    30 cm: (5,12,13)
    36 cm: (9,12,15)
    40 cm: (8,15,17)
    48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

    120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?

12cm는 선을 구부려서 만들 수 있는 세 변이 모두 정수인 직각삼각형 둘레의 최소값이다. 그리고, 더 많은 예가 있다:

    12 cm: (3,4,5)
    24 cm: (6,8,10)
    30 cm: (5,12,13)
    36 cm: (9,12,15)
    40 cm: (8,15,17)
    48 cm: (12,16,20)

이와 대비되게, 20cm 길이로는 변이 정수인 직각삼각형을 만들 수 없으며, 어떤 길이로는 1개 이상의 직각삼각형을 만들 수 있다. 예를 들어, 120cm로는 세가지의 변이 정수인 직각삼각형을 만들 수 있다.

    120 cm: (30,40,50), (20,48,52), (24,45,51)

L이 선의 길이이고 L이 150만 이하일 때, 1개의 직각삼각형만 만들 수 있는 L은 몇 개 있는가?

--------------------------------------------------------------------------

75번 문제인 것을 보면 좀 더 슬기롭게 해결하기를 요구하는 것 같은데, 문제와 관련되어 아는 공식은 피타고라스 정리 밖에 없으므로, 세 변의 길이가 L이고(a+b+c=L), 짧은 두 변 제곱의 합이 긴 변 제곱과 같다는(a²+b²=c²) 두가지를 이용해 문제를 해결하기로 했다.

실행시간이 너무 많이 걸려, L, a 기준으로 문제에서 제시한 공식을 다시 정리해서 c=(a²+(L-a)²)/2(L-a), b=L-a-c를 구하는 형태로 바꿔보았다.  이 경우에 L은 짝수인 경우에만 계산하도록 해서 시간도 조금 단축시킬 수 있었다. a값이 가장 큰 경우가 a와 b의 값이 같은 때이고, 이 경우 세 변의 합 L=(2+√2)a이며, a=L/(2+√2)a가 된다.

이렇게 범위를 가능한 줄여봤지만 L이 커지면서, a범위도 따라 커져서 실행시간은 여전히 만족스럽지 못했다. L이 10,000 커질때마다 실행시간이 15~20초씩 이전보다 늘어나고 있어 대략 50시간 정도 필요한 것으로 계산되었다.

어쩔수 없이 수학이론의 힘을 빌렸는데, m>n, m+n은 홀수, m과 n의 최대공약수는 1이라는 특성을 가지고 있으며, a=2mn, b=m²-n², c=m²+n²라는 공식이 있었다. 실제로 계산해보니 여기서 두 수의 값에 따라 제일 짧은 변이 a, b 중에 있을 수 있고, m=2, n=1일때 a=4, b=3, c=5(둘레 12)라는 직각삼각형을 구했으면, 전체 길이가 150만 이하일때까지 계속 곱해서 같은 비례를 가지는 직각삼각형을 모두 구해야 한다.

이렇게 구한 직각삼각형을 대상으로 둘레가 같으면서 a, b, c가 다른 경우를 제외하는 과정을 거치면 되는데, 참고로 150만 이하의 직각삼각형 조합이 백만개가 넘기 때문에 같은 값이 없을 때 리스트에 추가하는 것 보다는 집합을 이용하는 것이 속도가 월등히 빠르게 나왔다.

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

피타고라스 세 쌍은 a<b<c이며, a² + b² = c²인 자연수 3개를 말한다.

예를 들어, 3² + 4² = 9 + 16 = 25 = 5²이다.

a+b+c=1000인 피타고라스 세 쌍은 정확히 하나가 있다.

세 수의 곱을 구하시오.

--------------------------------------------------------------------------

많이 들어왔던 직각삼각형의 세 변을 구하는 피타고라스의 정리를 활용한 문제이다.

a는 1, b는 a+1에서 시작해서 1씩 키워가면서 두 수의 제곱의 합이 1000-a-b의 제곱인지 확인하는 형태로 구하였다. 단순하게는 반복 횟수가 a=998, b=999이지만, 조금 더 생각해서 이 숫자를 낮추는 것이 정답을 빨리 구하는 방법이 될 것이다.