Project Euler Problem9

Problem 9

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

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

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

나의 풀이)

처음엔 a + b + c를 제곱하여 피타고라스를 이용해 항 하나를 지워 구했더니.

4승이 나와 값을 비교하기에 크기가 너무 커졌다.

그래서 그냥 돌렸다. for문 3개로 구현하는게 굉장히 찝찝하지만;; 뭐 루프가 길것같지 않아 일단 수행!

역시 답이 금방 나왔다... 결론은 발코딩.

3중 for문(i = 1, j = i, k = j, 크기 조건때문에)

if(피타고라스 조건 && 합조건) return sum;

다른 사람의 풀이)

어떻게 풀었는지 궁금해 알고리즘들을 찾아봤다.

Without programming: a= 2mn; b= m^2 -n^2; c= m^2 + n^2; a + b + c = 1000; 2mn + (m^2 -n^2) + (m^2 + n^2) = 1000; 2mn + 2m^2 = 1000; 2m(m+n) = 1000; m(m+n) = 500; m>n; m= 20; n= 5; a= 200; b= 375; c= 425;

이렇게 쉽게 찾아내긴 하는데.. 

피타고라스 공식을 부정방정식으로 하면 저렇게 된다.

이걸 생각해내다니..!!