반응형
문제
영문
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
반응형
'🖥️ 문제 풀이 > 프로젝트 오일러' 카테고리의 다른 글
[프로젝트 오일러] 문제8 - 시리즈에서 가장 큰 곱 (0) | 2022.09.10 |
---|---|
[프로젝트 오일러] 문제7 - 10001번째 소수 (0) | 2022.09.09 |
[프로젝트 오일러] 문제6 - 합 제곱 차 (0) | 2022.09.09 |
[프로젝트 오일러] 문제5 - 최소공배수 (0) | 2022.09.09 |
[프로젝트 오일러] 문제4 - 가장 큰 대칭수 (0) | 2022.09.09 |
댓글