프로젝트 오일러 009

세 변의 길이가 모두 자연수이면서 그 길이의 합이 1000인 직각삼각형을 찾고 그 직각 삼각형의 세 변의 길이의 곱을 계산합니다.

우리는 이 문제에 대한 나이브한 풀이를 쉽게 생각할 수 있습니다.

1~1000 사이의 자연수 A를 하나 고릅니다.
다른 자연수 B도 하나 고릅니다.
C는 고를 필요가 없습니다. 문제에서 세 변의 합의 길이가 1000이라고 했으니, 1000 - A - B 하면 되겠네요.
세 변이 피타고라스 정리를 만족하는지 확인합니다.

그리고 **문제는 친절하게도 이 조건을 만족하는 삼각형은 하나 밖에 없다고 했습니다. ** 사실 이것이 문제의 난이도를 크게 낮추는 가장 중요한 힌트입니다.

여기에 A < B < C 라는 조건을 하나 더 세워서 올바르게 루프를 돌게 한다면 간단히 구할 수 있습니다.

def solve_a():
    for b in range(1, 1000):
        for c in range(b + 1, 999 - b):
            a = 1000 - b - c
            if a < 1:
                break
            if a * a + b * b == c * c:
                return a * b * c

if __name__ == '__main__':
    print(solve_a())

피타고라스 삼조

피타고라스 성질을 만족하는 세 개의 정수 (a, b, c)를 피타고라스 삼조라고 합니다. 각 수에 같은 값을 곱해도 피타고라스 정리의 식은 성립하므로, 피타고라스 삼조의 배수들도 피타고라스 삼조입니다.

각 성분이 서로 소인 피타고라스 삼조를 원시 피타고라스 삼조라고 하는데, 원시 피타고라스 삼조는 서로 소인 두 정수 m, n 이 있으면 얼마든지 만들어 낼 수 있습니다.

두 정수 m, n 중 하나는 짝수입니다.
m, n은 서로소입니다.
m > n 이라고 하면, 다음 수들은 원시 피타고라스 삼조가 됩니다.
$(m^{2} - n^{2}, 2 mn, m^{2} + n^{2})$

이 성질을 사용하여 적절한 범위 내에서의 m, n을 통해 피타고라스 삼조를 만들고, 그 합이 1000의 약수라면 몫을 곱하여 세 변을 찾을 수 있습니다.

이 방식은 되려 복잡해 보이지만, 실질적으로는 루프의 횟수 자체를 크게 줄이기 때문에 훨씬 빠르게 작동합니다. (gcd() 함수는 이전에 작성한 것을 참고하세요)

def solve_b():
    limit = int(500 ** 0.5)
    for m in range(1, limit):
        for n in range(1, m):
            if m * n % 2 > 0 or gcd(m, n) > 1:
                break
            a = m * m - n * n
            b = 2 * m * n
            c = m * m + n * n
            q, r =  divmod(1000, (a + b + c))
            if r == 0:
                return a * b * c * q**3