세 변의 길이가 모두 자연수 {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]))