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

직각 삼각형 중에서는 정삼각형은 나올 수 없기 때문에 길이를 작은 순서대로 a, b, c라 하면 가 된다.  b는 c 보다 작으므로 b의 범위는 이다. b가 어떤 값으로 정해졌을 때 a는 1~b 까지의 범위를 갖게 된다.

이 범위 내에서 루프를 돌면 a, b 가 어떤 값을 가질 때 c의 값은 이미 결정된 상태이고, 세 수가 피타고라스 정리를 만족하는지 검사한다. 만족하는 케이스가 나올 때마다 카운트를 세어서 각 p에 대해 조건을 만족하는 케이스가 몇 개나 되는지 센다. 이는 p를 key로 가지는 캐시가 필요하다는 뜻인데, 키 자체가 정수 타입이고 1000이하의 모든 자연수가 될 것이기 때문에 연속된 정수배열을 써도 무방하다.

모든 p에 대해서 만들 수 있는 직각 삼각형을 센 후에 그중 최대값을 찾고, 최대값을 가지는 인덱스를 찾으면 끝.

아래는 파이썬 풀이다.

def e39():
    borderlines = [0] * 1001
    for b in range(1, 500):
        for a in range(1, b+1):
            c_square = a**2 + b**2
            c = c_square ** 0.5
            if a+b+c > 1000:
                break
            elif (c == int(c)):
                borderlines[a+b+(int(c))] += 1
    print(borderlines.index(max(borderlines)))
%time e39()
# 840
# Wall time: 370 ms

아래는 동일한 알고리듬으로 작성한 Swift 풀이이다. (timeit은 간이 수행 시간 측정 함수)

import Foundation
func timeit(_ f: () -> ()) {
  let begin = Date()
  f()
  let elapsed = Date().timeIntervalSince(begin)
  print("time: \(elapsed * 1000)ms")
}
func findMax  (_ list: [T]) -> T {
  return list.reduce(list.first!){ $0 > $1 ? $0 : $1 }
}
let e39:() -> () = {
  var memo = Array(repeating:0, count: 1001)
  for b in 1..<500 {
    for a in 1...b {
      let c = Int(floor(sqrt(Double(a*a + b*b))))
      if a+b+c > 1000 {
        break
      } else if c*c == a*a + b*b {
        memo[a+b+c] += 1
      }
    }
  }
  let maxIndex = findMax(memo)
  print(memo.index{$0 == maxIndex}!)
}
timeit(e39)