[프로젝트 오일러] 문제9 - 특별한 피타고라스 트리플

문제

영문

Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a² + b² = c²
For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.Find the product abc.

바로가기

 

한글

세 자연수 a, b, c 가 피타고라스 정리 a² + b² = c² 를 만족하면 피타고라스 수라고 부릅니다 (여기서 a < b < c ).
예를 들면 3² + 4² = 9 + 16 = 25 = 5²이므로 3, 4, 5는 피타고라스 수입니다.
a + b + c = 1000 인 피타고라스 수 a, b, c는 한 가지 뿐입니다. 이 때, a × b × c 는 얼마입니까?

바로가기

 

해설

파이썬 (Python) + 수학적 해결법

방법0

a, b가 1부터 1000일 때까지 모든 경우의 수를 살펴봅니다. 느리고 비효율적입니다.

 

방법1

b>a이고, a² + b² = (s - a - b)²일 때 수학적으로 a≤(s-3)/3, b<(s-a)/2를 만족한다 합니다.

s = 1000
for a in range(1, (s-3)//3+1):
    for b in range(a+1, (s-a)//2):
        c = s-a-b
        if a*a + b*b == c*c:
            print(a*b*c)

 

방법2

피타고라스 트리플(Pythagorean triple)이라는 개념이 있습니다. 이는 피타고라스 정리를 만족하는 세 정수를 뜻합니다. 여기서 원시 피타고라스 트리플은 이 세수가 모두 서로소인 경우입니다.

 

(m²−n²,2mn,m²+n²)

 

피타고라스 트리플들은 다음과 같은 꼴을 만족한다고 합니다. 여기서 m과 n이 서로소이면 원시 피타고라스 트리플이라고 하네요!

 

a + b + c = 2m(m+n)

 

위와 같은 피타고라스 트리플이 성립할 때 다음과 같은 식이 성립합니다. 이를 만족하는 m과 n을 찾아주면 됩니다. 

for n in range(2, 1001):
    m = n
    while m*(m+n) < 500:
        m += 1
    if m*(m+n) == 500:
        break

a = m*m - n*n
b = 2*m*n
c = m*m + n*n

print(a*b*c)

 

방법3

위에서는 m과 n이 서로소가 아닌 경우를 살펴봤지만, 이번에는 m과 n이 서로소인 원시 피타고라스 트리플을 생각해봅시다! 그럼 우리가 구하려는 피타고라스 트리플은 여기서 일정 수를 곱한 형태일 것입니다.

 

a + b + c = 2m(m+n)d

 

식으로 정리해두면 다음과 같은 상태입니다. 여기서 m+n을 k라 이름 붙입시다. 

s2 = 1000//2
for m in range(2, s2**2):
    if s2%m == 0:
        sm = s2//m

        while sm%2 == 0:
            sm //= 2 #2 인수 제거
            
        k = m+2 if m%2 == 1 else m+1

        while k<2*m and k<=sm:
            if sm%k == 0 and gcd(k,m) == 1:
                d = s2//(k*m)
                n = k-m
                a = d*(m*m-n*n)
                b = 2*d*m*n
                c = d*(m*m+n*n)
                print(a*b*c)
            k += 2

그럼 다음과 같이 구할 수도 있습니다. 여기서 중간에 나온 gcd 함수는 최대공약수를 구하는 함수입니다. 최대공약수에 대해서는 해당 글을 참고해주세요!

 

 

C

#include<stdio.h>
int main(void) {
	int a = 2, b = 1;
	while (a<=1000) {
		b = a;
		while (b*(a + b) < 500) {
			b++;
		}
		if (b*(a + b) == 500) {
			break;
		}
		a++;
	}
	printf("%d:%d,%d,%d",a, b*b - a * a, 2 * a*b, b*b + a * a);
	printf("\n%d", (b*b - a * a)* (2 * a*b)* (b*b + a * a));
}

방법 2로 풀어낸 풀이입니다!

 

정답

31875000