프로젝트 오일러 143번

Let \(\rm ABC\) be a triangle with all interior angles being less than \(120\) degrees. Let \(\rm X\) be any point inside the triangle and let \({\rm XA}=p,\; {\rm XC}=q\), and \({\rm XB}=r\).

Fermat challenged Torricelli to find the position of \(\rm X\) such that \(p+q+r\) was minimized.

Torricelli was able to prove that if equilateral triangles \(\rm AOB, \; BNC\) and \(\rm AMC\) are constructed on each side of triangle (\rm ABC\), the circumscribed circles of \(\rm AOB, \; BCN\), and\(\rm AMC\) will intersect at a single point, \(\rm T\), inside the triangle. Moreover he proved that \(\rm T\), called the Torricelli/Fermat point, minimizes \(p+q+r\). Even more remarkable, it can be shown that when the sum is minimized, \({\rm An+BM=CO}=p+q+r\) and that \(\rm AN,\;BM\) and \(\rm CO\) also intersect at \(\rm T\).

If the sum is minimized and \(a, \;b,\; c\; p,\; q\) and \(r\) are all positive integers we shall call triangle \(\rm ABC\) a Torricelli triangle. For example, \(a=399, \;b=455,\; c=511\) is an example of a Torricelli triangle, with \(p+q+r=784\).

Find the sum of all distinct values of \(p+q+r \le 120000\) for Torricelli triangles.

---

내각이 모두 \(120 ^{\rm o}\) 미만인 삼각형 \(\rm ABC\) 내부에 \({\rm XA}=p, \; {\rm XC}=q,\; {\rm XB}=r\) 인 한 점 \(\rm X\) 가 있다.

페르마는 토리첼리에게 \(p+q+r\) 이 최소가 되는 점 \(\rm X\) 를 찾을 수 있는지 물었고, 토리첼리는 이에 대해 다음과 같은 결론을 도출해 냈다.

삼각형 \(\rm ABC\) 의 세 변을 한 변으로 하는 정삼각형 \(\rm AOB, \; BNC, \; AMC\) 를 그리고, 이 정삼각형들의 외접원을 그리면, 이 외접원들이 삼각형 내부의 한 점 \(\rm T\) 에서 만나게 되는데, 바로 이 점이 \(p+q+r\) 을 최소로 하는 점이라고 했고 이름하길 토리첼리/페르마 포인트라고 했다. 더 놀라운 사실은 이때 \({\rm AN=BM=CO}=p+q+r\) 이 되고, 선분 \(\rm AN, \; BM, \; CO\) 가 점 \(\rm T\) 에서 만나다는 것을 알아냈다. 

만약 \(p+q+r\) 이 최소가 될 때, \(a, \; b, \; c,\; p,\; q,\;r\) 이 모두 자연수이면 삼각형 \(\rm ABC\) 를 토리첼리 삼각형이라고 부른다. 예를 들어, \(a=399, \; b=455,\; c=511\) 이면 토리첼리 삼각형이 되는데, 이때 \(p+q+r=784\) 가 된다.

\(p+q+r \le 120000\) 범위에서 토리첼리 삼각형들의 \(p+q+r\) 의 값을 모두 더하면 얼마일까?

사각형 \(\rm AMCT\) 를 생각해 보자. 이 사각형은 원에 내접한 사각형이므로 마주보고 있는 두 각 \(\angle {\rm AMC}\) 와 \(\angle {\rm ATC}\) 의 합은 \(180^{\rm o}\) 가 되어야 한다. \(\angle {\rm AMC} = 60^{\rm o}\) 이므로 \(\angle {\rm ACT} = 120^{\rm o}\) 가 된다. 이런식으로 생각하면 \(\angle {\rm ATB}= \angle {\rm BTC}=120^{\rm o}\) 인것을 알 수 있다. 따라서 \(\triangle {\rm ATB}, \; \triangle {\rm BTC}, \; \triangle {\rm CTA}\) 에 대하여 제2코사인 법칙을 적용하면 \(\cos \left ( 120^{\rm o} \right) = - \dfrac{1}{2}\) 이므로 다음의 결과를 얻는다. 

\[a^2 = q^2 + r^2 - 2qr \cos \left (120^{\rm o} \right ) = q^2 + r^2 + qr\]

\[b^2 = p^2 + q^2 + pq\]

\[c^2 = r^2 + p^2 + pr\]

그래서 일단 우리가 해야할 일은 \(t^2 + s^2 + ts\) 가 완전제곱수가 되는 자연수 \((t, \;s)\) 의 순서쌍 (이런 경우를 완전제곱 쌍이라고 부르기로 하자)을 찾는 일이다. 139번 문제에서 피타고라스 수를 찾는 방법을 기억하는가? 이와 비슷하게 \(t^2 + s^2 +ts\) 가 완전제곱수가 되는 두 자연수 \(t, \;s\) 를 찾는 방법이 있는데, 다음과 같다. \(x, \; y\;\;(x>y)\) 가 서로소인 두 자연수이고, \(x-y\) 를 3으로 나누어 떨어지지 않을 때, 

\[t = 2xy+y^2\]

\[s=x^2 - y^2\]

위에서 구한 순서쌍 \((t, \;s)\) 와 이들의 정수배인 \((kt, \; ks)\) 쌍은 모두 완전제곱 쌍이 된다. 또한 \((s, \;t)\) 나 \((ks, \; kt)\) 역시 완전제곱 쌍이 되는 것을 알 수 있다.  자세한 방법은 여기 에서 확인할 수 있다.

위의 방법을 이용하면 \(t+s \le 120000\) 의 범위내에서 모든 완전제곱 쌍을 쉽게 구해낼 수 있다.  

이렇게 구한 완전제곱 쌍들을 그룹핑을 해야 하는데, \((t, \;s)\) 의 순서쌍에서 앞 요소인 \(t\) 들이 같은 것들끼리 그룹핑을 한다. 예를 들어, \((20, \;12), \;(20,\;64)\) 는 모두 완전제곱 쌍인데 이들을  하나로 묶는 작업을 해야 하는 것이다. 파이썬에서는 사전(dictionary) 가 있기 때문에 \(\{ 20:[12, 64] \}\) 처럼 완전제곱 쌍의 앞 요소를 key로 뒷 요소를 모아서 만든 리스트를 value로 지정하였다. 이렇게 완전제곱쌍들을 그룹핑을 한다. 

사실 완전제곱 쌍을 모두 찾아내고 그룹핑을 하는데 상당히 많은 시간이 걸린다. 따라서 이 작업의 결과를 텍스트 파일로 저장한 후에, 나중에는 그룹핑 결과를 파일에서 불러와 사용하는 방법을 이용하였다. 병렬처리라는 방법이 있다고는 하는데, 아직 그런걸 구사할 고수가 아니기 때문에 일단은 꼼수로 이런 방법을 .... (ㅠㅠ)

이제 사전의 value 인 리스트의 길이가 \(1\) 인 아닌 경우에 대해서 \((t, \; s), \; (t, \; u)\) 인 두 개의 완전제곱 쌍을 찾아낸다. 이때, \(s\) 와(u\) 는 key가 \(t\)인 것들의 value에 해당하는 리스트에서 순열을 이용하여 두 개의 수를 선택하면 된다. 이제 key가 \(s\) 인 value에 해당하는 리스트에 \(u\) 있는 것을 확인하거나 key가 \(u\) 인 value 에 해당하는 리스트에 \(s\) 가 있는지 확인하면 된다. 만약 그렇다면 \(t, \; s, \;u\) 는 우리가 찾던 \(p, \; q, \; r\) 이 되는 것이다.  따라서 이런 경우의 \(t+s+u\) 의 값들을 모두 더해주면 원하는 답을 얻을 수 있다.  

조건을 만족하는 \(t, \; s, \; u\) 를 찾아내는 과정을 다음과 같다. 

from itertools import permutations

f = open("pe143.txt", 'r')
lines = f.readlines()
f.close()

pairsdic = eval(lines[0])
result = []
for i in pairsdic:
    if len(pairsdic[i]) == 1:
        continue
    for j in permutations(pairsdic[i], 2):
        if j[0] not in pairsdic:
            continue
        if j[1] in pairsdic[j[0]]:
            temp = i + j[0] + j[1]
            if temp <= 120000 and temp not in result:
                result.append(temp)

print(sum(result))

여기서 'pe143.txt' 는 그룹핑된 결과 (key:value 로 이루어진) 를 저장한 텍스트 파일이다.