[C/C++] 프로젝트 오일러 #39 : 길이가 정수인 직각삼각형

프로젝트 오일러 #39는 난이도 5% 문제로 어렵지 않은 문제입니다.  제목에서 알 수 있듯이 피타고라스 삼각형 문제입니다.

 

직각삼각형의 길이가 정수로 나오는 것을 피타고라스 삼각형이라고 하는데요.  피타고라스 삼각형은 이미 공식화되어서 잘 나와 있습니다.

 

일단 피타고라스 삼각형의 원시근에 대해서 알아야 합니다.  세변의 길이를 a, b, c 라 하고, 직각의 대변의 길이를 c 라고 한다면, 우리가 잘 알고 있는 피타고라스 법칙이 나옵니다.

 

\[ a^2 + b^2 = c^2 \]

 

위 식을 만족하는 정수로 된 순서쌍 \( (x, y, z) \)가 있다면, 어떤 상수 c에 대해서 \( (cx, cy, cz) \)도 피타고라스 법칙을 만족하게 됩니다.   피타고라스 삼각형의 원시근은 순서쌍이 서로 소인 수를 말합니다.  이러한 순서쌍을 만드는 생성법칙은 아주 간단합니다.  그리고 이 생성법칙은 프로젝트 오일러 문제들 중에 활용할 경우가 아주 많습니다.

 

두 수 m, n에 대하여, \( (m, n) = 1 \),  \( m+n \) 은 홀수를 만족한다면, \( a = m^2 - n^2\), \(b = 2mn \), \(c = m^2 + n^2 \)라는 원시근을 가집니다.

 

Pythagorean triangles

 

제가 이 문제를 풀기 위해서는 이 법칙에 따라서 충분한 숫자 범위안에 있는 원시근을 찾았습니다.  그런 후, 모든 경우에 대해서 원시근의 배수가 되는지 검사를 하였습니다.

//------------------------------------------------
//    Project Euler #39 - Integer Right Triangles
//        - by Aubrey Choi
//        - created at 2015-03-22
//------------------------------------------------
#include <stdio.h>

#define    MAXLEN    1000

int gcd(int a, int b);

int main()
{
    int s, t;
    int pn[10000];
    int count = 0;

    for( int s = 2 ; s*s < MAXLEN/2 ; s++ )
    {
        for( int t = s-1 ; t >= 1 ; t -= 2 )
        {
            if( gcd(s, t) != 1 ) continue;

            int len = 2*s*s + 2*s*t;
            if( len > MAXLEN ) break;

            pn[count++] = len;
        }
    }

    int max = 0;
    int maxlen = 0;
    for( int i = pn[0] ; i <= 1000 ; i++ )
    {
        int t = 0;
        for( int j = 0 ; j < count ; j++ )
            if( i%pn[j] == 0 ) t++;
        if( max < t ) { max = t; maxlen = i; }
    }

    printf("ans = %d\n", maxlen);
}

int gcd(int a, int b)
{
    while( b )
    {
        int t = b;
        b = a%b;
        a = t;
    }
    return a;
}

 

일단 gcd(a, b) 함수는 a와 b의 gcd 값을 구합니다.  m, n의 조건중에 서로 소라는 조건이 있으니까요.  그리고 main() 함수 전반부에서 피타고라스 삼각형의 원시근을 구하고, 둘레의 길이를 pn[] 배열에 저장합니다.  main() 함수 후반부에서는 pn[0]~1000 숫자 범위 안에 있는 숫자 중에 pn[] 배열값으로 나누어 떨어지는지 검사를 하였습니다.

 

사실 위 프로그램은 속도를 위해서 더 개선할 수 있는 부분들이 많습니다.  나중에 프로젝트 오일러 #78의 경우 속도를 개선하지 않으면 쉽게 답이 나오지 않거든요.