가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는?

[eng][kor]


아주 느린 풀이

단순하게 이중 for loop 를 돌면서 가능한 삼각형 변 길이를 구하고, 이 변 길이에 대해 직각삼각형 여부를 따져 보는 방식이다. 답은 구해냈지만 실행시간이 148초가 걸리고.. 둘레가 커질수록 연산 속도도 느려지는 것을 체감하는 비효율적인 풀이.

뭔가 러시안 페인트공 알고리즘이 생각난다. ^^;;

/*
  Problem 39 - Integer right triangles 
*/

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

bool isRightAngle( int a, int b, int c)
{
	return (a*a + b*b == c*c);
}

int getRightAngleTriangles( int a[], int len)
{
	int nRightAngle = 0;
	for(int i=1; i<len; i++)
	{
		for(int j=1; j<len-i; j++)
		{
			std::vector<int> abc;
			abc.push_back( i);
			abc.push_back( j);
			abc.push_back( len-i-j);
			std::sort( abc.begin(), abc.end());

			if (isRightAngle( abc[0], abc[1], abc[2])) {
				nRightAngle++;	
			}
		}
	}
	return nRightAngle;
}

int main(int argc, char** argv)
{
  clock_t begin = clock();
 
	/* starting code */
	int arr[3] = {0,};

	int maxtriangles = 0;
	int maxlen = 0;
	for(int i=3; i<=1000; i++)
	{
		cout << "i=" << i << endl;
		int triangles = getRightAngleTriangles( arr, i); 
		if (triangles > maxtriangles) {
			maxtriangles = triangles;
			maxlen = i;
		}
	}

	cout << "maxtriangles = " << maxtriangles << " at " << maxlen << endl;
  /* end of code */

  clock_t end = clock();
  std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
  return 0;
}


개선한 풀이

어디서 개선할 수 있을지 한번 생각해보자.

getRightAngleTriangles 에서 벡터를 선언하고 여기다 세 변을 push한 후 정렬하는 이유는 isRightAngle의 마지막 인자값으로 세 변의 길이 중 가장 큰 값을 넣어주기 위해서이다. 마지막 인자값에 가장 큰 값을 넣는 과정을 좀더 효율적으로 할 수 없을까?

첫번째 수 i를 삼각형의 가장 큰 변의 길이라고 하자. 두번째 변과 세번째 변의 길이가 i를 넘지 않도록 i를 세변의 합 len의 3분의 1보다는 항상 크도록 범위를 지정한다. 두번째 변의 길이 j 의 루프가 남은 변의 길이의 절반을 넘지 않도록 한다.

이렇게 하면 i가 가장 큰 변의 길이임이 보장되므로 벡터,정렬 코드를 뺐고 중복계산이 사라졌다.

int getRightAngleTriangles( int a[], int len)
{
  int nRightAngle = 0;
  for(int i=len-2; i>=len/3; i--)
  {
    for(int j=1; j<=(len-i)/2; j++)
    {
      if (isRightAngle( j, len-i-j, i)) {
        nRightAngle++;
      }
    }
  }
  return nRightAngle;
}

실행해보니 0.22초가 걸린다. 훨씬 좋아졌다.

역발상

보다 아름다운 풀이가 있다.

오일러 39번 문제는 a + b + c = p 인 p 중 a^2 + b^2 = c^2 를 만족하는 경우가 가장 많은 p를 찾는 것인데, 역발상으로 a^2 + b^2 = c^2 식을 먼저 체크하는 것이다.

a와 b를 휴리스틱하게 500 정도까지 상한을 잡고, sqrt( a^2 + b^2)가 정수이면 p를 구해 1000 이하이면 p를 인덱스로 하여 메모해 둔다. 마지막에 메모를 돌며 모든 인덱스에서 맥스값인 인덱스를 구한다.

신선하지 않나? 바로 c++ 버전으로 구현해 봤다.

/*
  Problem 39 - Integer right triangles 
*/

#include <iostream>
#include <ctime>
#include <cmath>
#include <map>

using namespace std;

int main(int argc, char** argv)
{
  clock_t begin = clock();

  /* starting code */
  std::map<int,int> triangles;
  std::map<int,int>::iterator it;

  for(int a=1; a<=500; a++)
  {
    for( int b=1; b<=500;b++)
    {
      double d = sqrt( a*a+ b*b);
      int c = int(d);
      if( (d == c)) {
        int p = a+b+c;
        if( p <= 1000) {
          it = triangles.find( p);
          if( it != triangles.end()) {
            (it->second)++;
          } else {
            triangles.insert( std::map<int,int>::value_type( p, 1));
          }
        }
      }
    }
  }

  int max = 0;
  int where = 0;
  for( it = triangles.begin(); it != triangles.end(); ++it)
  {
    if (max < it->second) {
      max = it->second;
      where = it->first;
    }
  }
  cout << "max = " << max << " at " << where << endl;
  /* end of code */

  clock_t end = clock();
  std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
  return 0;
}

실행시간은 조금씩 다르지만 0.013초를 넘지 않는다. 이정도면 훌륭하다.