콘텐츠로 건너뛰기
Home » 오일러 프로젝트 009

오일러 프로젝트 009

둘레의 길이가 1000이고 각 변의 길이가 자연수인 직각삼각형 찾기

세 자연수 a, b, c 가 피타고라스 정리 a^2 + b^2 = c^2 를 만족하면 피타고라스 수라고 부릅니다 (여기서a \le b \le c ).
예를 들면 3^2 + 4^2 = 9 + 16 = 25 = 5^2 이므로 3, 4, 5는 피타고라스 수입니다.
a + b + c = 1000 인 피타고라스 수 a, b, c는 한 가지 뿐입니다. 이 때, a × b × c 는 얼마입니까?

삼각형의 세 변의 길이를 짧은 것 부터 a, b, c 라하자. ( a \le b \le c ) 이 때 a 가 가장 커질 수 있는 경우는 a = b = c, 즉 정삼각형이 되는 경우이다. 따라서 a는 둘레를 P라고 했을 때 1 ~ (P/3) 의 범위에 있을 수 있다. a가 특정한 값을 가진다고 하면 b는 a와 같거나 a를 제외한 둘레의 남은 길이의 절반에 이르는 범위를 가질 수 있다. 이 범위를 가지고 피타고라스 정리를 만족하는 경우를 검사한다. 문제에서는 둘레 1000일 때 이를 만족하는 조합은 단 한가지 경우 밖에 없다고 했으니, 해당 케이스를 찾으면 세 변의 길이의 곱을 출력하고 끝낸다.
Swift 코드는 아래와 같다.

let p = 1000 // 삼각형의 둘레
main: for a in 1..<(p / 3) {
// ^ "main"이라는 레이블을 붙인다.
  for b in a..<( (p - a) / 2) {
    let c = p - a - b
    if c * c == a * a + b * b {
      print(a * b * c)
      break main // 레이블을 이용해서 중첩 루프를 한 번에 빠져나간다.
    }
  }
}

그외 언어 풀이

모두 동일한 알고리듬으로 코딩했다.

파이썬

파이썬 3.6이다. 특별한 테크닉은 사용하지 않았다.

def e009():
  p = 1_000
  for a in range(1, p // 3):
    for b in range(a, (p-a)//2):
      c = p - a - b
      if c*c == a*a + b*b:
         print(a*b*c)
         return
e009()

자바스크립트

문법외에 어떤 특별한 부분도 없다.

let e009 = () => {
  let p = 1000;
  for(var a = 0; a < p / 3; a++) {
    for(var b = a; b < (p-a)/2; b++) {
      let c = p - a - b;
      if(c*c==a*a+b*b) {
        console.log(a*b*c);
        return;
      }
    }
  }
}
e009()

개인적으로는 C 스타일의 for 문을 싫어하는데, 자바스크립트는 특정 범위를 만들 수 있는 리터럴이 없어서 답답하다. LiveScript에서는 아래와 같이 쓸 수 있다.

e009 = !->
  p = 1000
  for a from 1 to p / 3
    for b from a to (p - a) / 2
       c = p - a - b
       if c*c == a*a + b*b then
         console.log a * b * c
         return