Project Euler Problem9

2015. 2. 15. 01:14프로그래밍/알고리즘

728x90
728x90

Problem 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를 제곱하여 피타고라스를 이용해 항 하나를 지워 구했더니.

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;


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

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

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







728x90
반응형

'프로그래밍 > 알고리즘' 카테고리의 다른 글

Project Euler Problem16  (0) 2015.02.24
Project Euler Problem15  (0) 2015.02.17
Project Euler Problem10  (0) 2015.02.15
Project Euler Problem5  (0) 2015.02.12
Project Euler Problem7  (0) 2015.02.05
Project Euler Problem6  (0) 2015.02.05
Project Euler Problem4  (0) 2015.01.25