Project Euler - 문제 9번

Special Pythagorean triplet

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.

 문제 9번 : 피타고라스 triplet은 세 숫자의 집합으로,  a  b  c 이며, 다음의 조건을 만족한다. 예를 들어서, 3² + 4² = 9 + 16 = 25 = 5². 피타고라스 triplet 중에서 a + b + c = 1000을 만족하는 triplet은 오직 한 쌍이 존재한다. 이 때 abc를 구하여라.

---

 이 문제는 단순하게 계산하면 되기도 하지만, 빠른 속도로 결과를 구하기 위해서 위키피디아를 검색해 보았습니다. 그랬더니, Euclid's formula 라는 방법으로 세 숫자를 두 변수로 표현할 수 있고 또한 우리가 가진 조건을 통해서 보다 쉽게 답을 얻을 수 있습니다. 먼저, Euclid's formula를 살펴보면
$$a = m^{2}-n^{2}, \qquad b = 2mn, \qquad c = m^{2}+n^{2},$$이렇게 주어지고 여기서 조건은 \(m>n\) 입니다. 이 공식과 주어진 조건을 합하면,
$$a+b+c=2m(m+n)=1000, \quad \Rightarrow \quad m(m+n)=500.$$그러면, 우리가 \(m>n\) 이라고 했기 때문에 m이 가질 수 있는 최소 최대 값은 다음과 같이 얻을 수 있습니다.
$$ m^2 < m(m+n) = 500 < 2m^{2}.$$그러면 m의 값이 제약이 되므로 for문 하나는 위의 m에 대한 범위를 주고 다른 하나는 n을 1부터 m까지 주면 훨씬 짧은 시간 안에 피타고라스 triplet을 m과 n을 통해서 얻을 수 있습니다.

#include <iostream>
#include "time.h"
#include "math.h"
using namespace std;

#include <iostream>
#include "time.h"
#include "math.h"
using namespace std;

int main()
{
 clock_t start = clock();
 // Use Euclid's formula : a=m^2-n^2, b=2mn, c=m^2+n^2
 int result;
 for(int m = sqrt(500/2); m*m < 500; m++)
 {
  for(int n = 1; n < m; n++)
  {
   if(m*(m+n) == 500)
    result = (m*m-n*n)*(m*m+n*n)*2*m*n;
  }
 }
 
 clock_t end = clock();
    cout << "Result : " << result << endl;
    cout << "Time : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

 그러면 손쉽게 답을 얻을 수 있고 그 값은 아래와 같이 나옵니다.