Project Euler. #9. Special Pythagorean triplet

By | 2013/02/20

Project Euler (http://projecteuler.net/) 문제9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

피타고라스의 삼각쌍은 세 자연수에 대하여 a < b < c 이고,

a2 + b2 = c2

예를 들면, 32 + 42 = 9 + 16 = 25 = 5이다.

a + b + c = 1000 을 만족하는 피타고라스 삼각쌍은 오직 하나만 존재한다.

abc 곱셈의 결과를 구하여라.


for a in range(1, 999):
    for b in range(a+1, 1000):
        if a+b+(a*a+b*b)**(0.5)==1000:
            print a*b*((a*a+b*b)**(0.5))

간단히 이 문제를 해결하기 위해서 a, b, c를 찾기 위해 삼중 for문을 사용할 수도 있겠지만, 이 문제를 그렇게 비효율 적인 방법으로 풀고 싶지는 않았다. 시간 복잡도가 무려 O(n3) 이라니...

Pythagorean triplet을 만족하려면 각 a, b, c 는 0이 될 수 없다. 그러므로 a는 for문에서 1부터 시작하고, b는 a보다 크므로 for문에서 a+1부터 시작한다. 일단 문제에서 a2 + b2 = c2라고 주어졌기 때문에, c를 따로 for문을 이용하여 구할 필요는 없게되었다. c = \sqrt{a^2+b^2} 이다. 그러므로 a + b + c = 1000 인 경우는 파이썬 코드로 표현하면 a+b+(a*a+b*b)**(0.5)==1000 이 된다.

삼중 for문을 써서 구한 다른 여러 답들보다는 나의 풀이가 훨씬 뛰어나다고 생각하긴 하지만, 뭔가 또 색다른 해법이 있을 것 같아서 다른 사람들의 답들을 뒤져보던 중... 엄청난 수학자의 등장!


# Developed by johnnie on Project Euler
for m in range(1,22):
    for n in range(1,(500-int(m**2/m))):
        if m**2+m*n==500 and m>n:
            print((m**2-n**2)*(2*m*n)*(m**2+n**2))

Euclid's formula(http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple)를 이용하여 이 문제를 해결하셨다! 이런 듣도보도 못한 수학적 지식을 동원해서 문제를 해결하다니, 엄청난 고수다.

Euclid's formula에 대해 네이버에 검색해보니 중학생 수학에서 배우는 것이라는데... 나름 중2때, 수학 기말고사 시험에서 반에서 혼자 수학을 만점 받을 정도였는데도 전혀 기억이 나질 않는다. 중3때는 수학 시험에서 40점을 받을 정도로 공부를 안해서 그런가? 나이를 먹을 수록 학창 시절에 공부를 그리 열심히 하지 않았던 것에 대한 후회가 점점 더 심해진다. ㅠㅠ