오일러 프로젝트 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]))