39. 프로젝트 오일러 #39 : 길이가 정수인 직각삼각형

난이도 5% 문제입니다.

이번 문제는 피타고라스 삼각형 문제네요.

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

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

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

두 수 m, n에 대하여,

1. (m, n) = 1

2. m+n 은 홀수

를 만족한다면,

이라는 원시근을 가집니다.

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

#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의 경우 속도를 개선하지 않으면 쉽게 답이 나오지 않거든요.