오일러 프로젝트 75

문제

긴 철사를 구부려서 세 변이 정수인 직각 삼각형을 만들 때, 그 방법이 한 가지 뿐인 경우는 12cm를 최소로 해서 아래와 같이 여러 개가 있습니다. 

12cm: (3, 4, 5)
24cm: (6, 8, 10)
30cm: (5, 12, 13)
36cm: (9, 12, 15)
40cm: (8. 15, 17)
48cm: (12, 16, 20)

반면에, 20cm의 경우 처럼 세 변이 정수인 직각 삼각형을 만들 수 없을 때도 있고, 여러 종류의 직각 삼각형을 만들 수 있을 때도 있습니다. 예를 들어 120cm의 철사로는 세 가지의 서로 다른 직각 삼각형이 만들어집니다. 

120cm: (30, 40, 50), (20, 48, 52), (24, 45, 51)

그러면 길이가 백오십만(1,500,000)이하인 철사를 가지고 세 변이 정수인 직각삼각형을 만들 때, 그 길이로는 한가지 방법으로만 만들 수 있게 되는 경우는 모두 얼마나 됩니까?

접근

어찌보면 간단한 수 같아 보일 수도 있다. 키가 12~1,500,000 의 정수 수열인 사전을 준비하고, 합이 1,500,000 이하인 세 정수 a, b, c 에 대해서 피타고라스 정리를 만족하는지를 검사하고, 검사하면 사전에 그 세수의 합에 해당하는 값을 1만큼 추가한다. 모든 과정이 끝나고나면 사전에서 값이 1인 키 값만 검사해서 합산하면 된다. 

문제는 이 전수조사의 양이 너무 많다는 것이다. 150만번만 돌면 되는 것도 아니고 각 길이 값 내에서 다시 a, b 값을 순차적으로 바꿔가면서 돌아야하니 인간적으로 계산해야하는 횟수가 너무 많다. 전수 조사라는 컨셉을 피해갈 수는 없으니 조사 대상을 극적으로 줄여서 성능을 끌어올릴 방법을 강구해야 한다. 

원시 피타고라스 수

흔히 ‘피타고라스 수’라고 하는데, 정확히는 ‘피타고라스 트리플(삼조)’이다. 피타고라스 삼조는 피타고라스 정리를 만족하는 세 양수의 튜플이다. 이 때 세 수가 서로 소라면 이를 원시 피타고라스 삼조라 한다. 

임의의 피타고라스 삼조에 대해 각 요소값을 n배 한 튜플 역시 피타고라스 삼조가 된다. 즉 만약 우리가 150만 미만의 원시피타고라스 삼조를 알고 있다면, 찾을 수 있는 모든 (a, b, c)의 조합은 이 원시피타고라스 삼조의 배수라는 뜻이다. 

원시 피타고라스 삼조는 서로 소인 두 홀수가 있다면 다음과 같이 생성가능하다. 

  • m * n
  • (m * m + n * n) / 2
  • (m * m – n * n) / 2

이를 이용해서 다음과 같이 피타고라스 삼조를 생성하는 함수를 만들 수 있다. 두 수가 서로 소가 아니거나,  둘 중 하나 이상이 짝수라면 None을 리턴하도록 한다.

def make_ps(m, n):
  m, n = (m, n) if m >= n else (n, m)
  if m % 2 is 0 or n % 2 is 0 or\
    gcd(m, n) > 1:
    return None
  a = m * n
  b = (m*m - n*n) // 2
  c = (m*m + n*n) // 2
  # 리턴시에는 작은 값부터 크기대로 정렬
  return (b, a, c)

입력값의 범위 제한

위 함수를 이용했을 때 n이 1이라면 m이 모든 홀수인 경우에 원시피타고라스 삼조를 만들 수 있다. 먼저 둘레가 150만이 될 수 있는 m, n 에 대해서 그 한계값을 찾아보자.

LIMIT = 1_500_000

def get_max_range():
  m = 3
  while True:
    s = make_ps(m, 1)
    if s is not None and sum(s) > LIMIT:
      return m
    m += 2

계산하기

이제 get_max_range()를 실행해서 얻게되는 한계값까지 m, n을 늘려가면서 피타고라스 삼조를 만든다. 여기서 주목할 것은 얻게되는 세 값의 합이다. 원시 피타고라스 삼조를 얻게되면 그 합으로부터 150만 이하의 값에 대해서 합의 정수배에 해당하는 둘레에는 한 가지 방법이 계속 추가된다. 이런식으로 리스트 하나에 각 인덱스에 해당하는 둘레값에서 만들 수 있는 직각삼각형의 개수를 계산해 나갈 수 있다.

참고로 원시피타고라스 삼조를 2중 리스트 축약으로 계산해되지만, 이렇게하면 쓸데없이 많은 루프를 돌게되므로(약 5초 가량 소요된다.)  2중 for 루프를 돌면서 한계값을 초과하는 시점에 중단하는 방식으로 루프의 수를 줄인다. 아래 코드로 계산했을 때 전체 수행시간은 대략 0.3~0.4초 가량.

def e075():
  max_range = get_max_range()
  # 원시 피타고라스 삼조 전체의 집합을 구한다.
  ps = set()
  for m in range(3, max_range, 2):
    for n in range(1, m, 2):
      p = make_ps(n, m)
      if p is not None:
        if sum(p) < LIMIT:
          ps.add(p)
        else:
          break
  # 직각삼각형을 만드는 경우의 수 세기
  ways = [0] * (LIMIT + 1)
  for p in ps:
    s = sum(p)
    for i in range(s, LIMIT, s):
      ways[i] += 1

  print(sum(1 for x in ways if x == 1))