오일러 프로젝트 39
세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은 아래와 같이 세 개가 있습니다.
{20, 48, 52}, {24, 45, 51}, {30, 40, 50}
p가 1000이하일 때, 세변의 길이가 모두 자연수인 직각삼각형을 가장 많이 만들 수 있는 p의 값은 얼마입니까?
http://euler.synap.co.kr/prob_detail.php?id=39
접근
어떤 고정된 p 값이 있을 때, 직각 삼각형의 빗변이 아닌 두 변의 길이를 a, b 라고 하자. (a, b는 정수, 0 < a < b) 정삼각형은 직각 삼각형이 아니며, 모든 변의 길이가 자연수가 되려면 이등변 직각 삼각형도 존재할 수 없다. 따라서 a < b < p – (a + b) 라는 부등식을 얻을 수 있고, 피타고라스 법칙에 따라 다음과 같은 조건들을 만족해야 한다.
\begin{align}
0 < a &< b \\
a < b &< p - (a +b) \\
a^2 + b^2 &= c^2 = (p - (a + b))^2 \\
0 < a &< p \div 3 \\
a < b &< (p \div 2 - 1)
\end{align}가장 작은 변은 p/3보다는 작아야 한다. 다른 하나의 변은 p/2-a보다는 작아야 한다. 해당 범위 내에서 가능한 정수 c가 존재하는지 찾고, 존재한다면 그 합인 p의 카운트를 올려준다. 추후 가장 높은 카운트를 가진 p를 찾으면 된다. 이렇게하면 p에 대해 루프를 돌지 않고도 필요한 전체 값에 대해 체크할 수 있다.
%%time
ps = [0] * 1001
for b in range(1, 500):
for a in range(1, b):
c = (a * a + b * b) ** .5
if a + b + c > 1000:
break
elif (c == int(c)):
ps[a + b + int(c)] += 1
print(max(enumerate(ps), key=lambda x: x[1]))피타고라스 삼조를 이용한 풀이
피타고라스 정리를 만족하는 세 개의 정수의 순서쌍 (a, b, c)를 피타고라스 삼조라 하고, 이 때 세 정수 a, b, c가 서로 소인 경우에는 특별히 원시 피타고라스 삼조라 한다. 모든 피타고라스 삼조는 원시 피타고라스 삼조의 각 정수의 배수이다. 따라서 특정 범위 이내의 원시 피타고라스 삼조를 구하면, 그 합이 1000 이하인 배수들까지 개수를 세는 것으로 이 문제를 풀 수 있다.
피타고라스 삼조는 서로 소인 두 정수 m, n (m > n) 에 대해서 (m2 + n2, 2mn, m2-n2)로 구할 수 있으며, 원시 피타고라스 삼조는 두 수 중 하나가 짝수일 때 해당한다. 원시 피타고라스 삼조의 합은 2m2 + 2mn 이며, 이 값이 1000 이하가 되는 경우 m은 500의 제곱근까지의 범위를 가질 수 있다.
# 서로 소를 검사하기 위해 gcd를 구하는 함수를 작성
def gcd(a: int, b: int) -> int:
if a < b:
return gcd(b, a)
r = a % b
if r == 0:
return b
return gcd(b, r)
ps = [0] * 1001
for m in range(2, int(500 ** .5 + 1.5):
for n in range(1, m):
if gcd(m, n) == 1 and m * n % 2 == 0:
p = 2 * m * (m - n)
for i in range(p, 1000, p):
ps[i] += 1
print(max((v, i) for (i, v) in enumerate(ps)))
