2015. 2. 15. 01:14ㆍ프로그래밍/알고리즘
Problem 9
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
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;
이렇게 쉽게 찾아내긴 하는데..
피타고라스 공식을 부정방정식으로 하면 저렇게 된다.
이걸 생각해내다니..!!
'프로그래밍 > 알고리즘' 카테고리의 다른 글
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 |