프로젝트 오일러 039

풀이

이 문제는 피타고라스 삼조를 사용하여 풀라는 의도가 느껴지지만, 사실 문제의 조건들을 잘 이용하면 더 간단하고 빠르게 풀 수 있습니다.

• 삼각형의 가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작습니다.
• 세 변의 길이가 같으면 직각 삼각형이 될 수 없습니다.
• 두 변의 길이가 같아도 직각 삼각형이 될 수 없습니다.

자, 자연수 a, b, c가 삼각형의 세 변의 길이라 하고, a < b < c 이며, p = a + b + c 라고 합니다. 이 때 세 자연수는 삼각형의 변의 길이에 해당하기 때문에 범위에 제약을 갖습니다. (모든 변의 길이가 자연수인 직각 이등변 삼각형은 존재할 수 없습니다.)

1. a < b < c 이므로 a < p ÷ 3 입니다.
2. a < b < p ÷ 2 입니다.
3. $a^2+b^2=c^2$을 만족합니다.

이 조건으로 범위를 제한하면 빠르게 계산이 가능합니다. 둘레의 합의 한계치는 1,000이므로 길이가 1001인 0으로 채워진 리스트를 만들고, 직각 삼각형을 만들 수 있는 세 변이 나타날 때 그 합을 인덱스로한 값을 증가시키면 각 둘레별로 만들 수 있는 직각 삼각형의 개수를 구할 수 있습니다. math.hypot()은 삼각형의 빗변의 길이를 구하는 함수입니다.

from math import hypot

def g():
    limit = 1000
    res = [0] * (limit + 1)
    for b in range(2, limit // 2):
        for a in range(1, b):
            c = int(hypot(a, b))
            d = a + b + c
            if d < limit and c * c == a * a + b * b:
                res[d] += 1
    print(max(list(enumerate(res)), key=lambda x: x[1]))

g()

피타고라스 삼조

세 자연수 (a, b, c)에 대해 이 값들이 피타고라스 정리를 만족하면 이를 피타고라스 삼조라고 합니다. 이 때 a, b, c 가 모두 서로 소인 경우를 ‘원시 피타고라스 삼조’라고 합니다. 모든 피타고라스 삼조들은 원시 피타고라스 삼조의 배수입니다.

피타고라스 삼조는 서로 소인 두 정수 m, n (m > n)이 있고, 둘 중 하나가 짝수일 때, $\left(m^2+n^2,2mn,m2-n^2\right)$으로 구할 수 있습니다. 원시 피타고라스 삼조를 만들었을 때, 세 요소 값의 합이 직각삼각형의 합이 되고, 한계값인 1,000보다 작은 그의 배수들 모두 직각 삼각형을 이룹니다. 따라서 배수와 그 합에서의 직각 삼각형의 개수를 기록하면 됩니다.

피타고라스 삼조의 합을 구하면 $2m(m+n)$이므로, m, n의 차가 가장 적을 때 최대가 된다고 보면 m은 500의 제곱근보다 작아야 합니다. 이 때의 루프 횟수는 매우 작기 때문에 엄청 빠르게 답을 낼 수 있습니다.

from math import gcd

def h():
    limit = 1000
    res = [0] * (limit + 1)
    for m in range(2, int((limit / 2)**0.5)):
        for n in range(1, m):
            if m * n % 2 == 0 and gcd(m, n) == 1:
                p = 2 * m * (m + n)
                for q in range(p, limit, p):
                    res[q] += 1
    print(max(list(enumerate(res)), key=lambda x: x[1]))

h()