[C/C++] 프로젝트 오일러 #94 Almost Equilateral Triangles(수학)

Project Euler #94: Almost Equilateral Triangles 문제는 “거의 정삼각형” 성질을 가진 삼각형 중에서 주어진 조건을 만족하는 삼각형의 합을 구하는 문제입니다.

 

정삼각형은 세 변의 길이가 모두 같은 삼각형입니다. 그러나 이 문제에서는 거의 정삼각형(Almost Equilateral Triangles)을 다룹니다. 거의 정삼각형은 다음 조건을 만족하는 삼각형입니다:
1. 두 변의 길이가 같고, 나머지 한 변의 길이가 이와 1 차이가 난다.  예:  \(a, a, a+1\)  또는  \(a, a, a-1\)  형태

2. 삼각형의 세 변이 정수이고, 넓이도 정수여야 한다.

삼각형의 넓이 계산 (헤론의 공식)

삼각형의 넓이를 구할 때는 헤론의 공식을 사용합니다.
세 변이 \(a, b, c\)인 삼각형의 넓이는 다음과 같이 계산됩니다:

\[ s = \frac{a + b + c}{2} \quad \text{(반둘레)} \]
\[A = \sqrt{s(s-a)(s-b)(s-c)}\]

여기서 \(A\)가 정수가 되려면 루트 내부의 값 \(s(s-a)(s-b)(s-c)\)가 완전제곱수여야 합니다.

예제를 들어보면 다음과 같습니다.

예제 1: \(a=5\)
삼각형의 변: \(5, 5, 6\)
\[s = \frac{5 + 5 + 6}{2} = 8\]
\[A = \sqrt{8 \cdot (8-5) \cdot (8-5) \cdot (8-6)} = \sqrt{8 \cdot 3 \cdot 3 \cdot 2} = \sqrt{144} = 12 \quad (\text{정수})\]
둘레는  \(5 + 5 + 6 = 16 \)입니다.

예제 2: \(a=17\)
삼각형의 변: \(17, 17, 16\)
\[s = \frac{17 + 17 + 16}{2} = 25\]
\[A = \sqrt{25 \cdot (25-17) \cdot (25-17) \cdot (25-16)} = \sqrt{25 \cdot 8 \cdot 8 \cdot 9} = \sqrt{14400} = 120 \quad (\text{정수})\]
둘레는 \(17+17+16 = 50\)입니다.

최종적인 목표는 둘레가 \( 10^9  \) 이하인 모든 거의 정삼각형을 찾아, 해당 삼각형의 둘레 합을 구하는 것입니다.

equilateral triangles

 

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #94 - Almost Equilateral Triangles
//        - by Aubrey Choi
//        - created at 2015-10-23
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

#define    LIMIT    1000000000

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

void solve1()
{
    int sum = 0;
    for(int m = 3 ; 3*m*m < LIMIT*2 ; m += 2 )
    {
        for( int n = 1 ; n < m ; n += 2 )
        {
            if( gcd(m, n) > 1 ) continue;
            int a = (m*m-n*n)/2;
            int b = m*n;
            int c = (m*m+n*n)/2;
            if( (2*(b+c) <= LIMIT) && ( c == 2*b-1 || c == 2*b+1 ) ) sum += 2*(b+c);
            if( (2*(a+c) <= LIMIT) && ( c == 2*a-1 || c == 2*a+1 ) ) sum += 2*(a+c);
        }
    }
    printf("Ans = %d\n", sum);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

 

이 코드는 정수론과 피타고라스 삼각형의 성질을 사용하여 둘레가 \(10^9\) 이하인 거의 정삼각형을 찾고, 그 둘레의 합을 계산합니다. 아래는 코드의 각 부분에 대한 상세 설명입니다.

1. 전역 상수 정의

#define LIMIT 1000000000

• 삼각형 둘레의 상한선. 둘레가 \( 10^9 \)를 초과하지 않도록 제한합니다.

2. 최대공약수(GCD) 계산 함수

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

• 유클리드 알고리즘을 사용하여 두 정수 a와 b의 최대공약수(GCD)를 계산합니다.
• 삼각형의 성질(특히 피타고라스 삼각형 생성)을 이용하기 위해 m과 n이 서로소인지 확인할 때 사용됩니다.

3. 문제 해결 함수: solve1

void solve1()
{
    int sum = 0; // 둘레의 총합
    for (int m = 3; 3 * m * m < LIMIT * 2; m += 2) // m은 홀수
    {
        for (int n = 1; n < m; n += 2) // n은 홀수
        {
            if (gcd(m, n) > 1) continue; // m과 n이 서로소가 아니면 건너뛴다

            int a = (m * m - n * n) / 2; // 첫 번째 변
            int b = m * n;               // 두 번째 변
            int c = (m * m + n * n) / 2; // 빗변

            // 조건 1: 둘레가 LIMIT 이하이고 c가 2b±1인 경우
            if ((2 * (b + c) <= LIMIT) && (c == 2 * b - 1 || c == 2 * b + 1))
                sum += 2 * (b + c);

            // 조건 2: 둘레가 LIMIT 이하이고 c가 2a±1인 경우
            if ((2 * (a + c) <= LIMIT) && (c == 2 * a - 1 || c == 2 * a + 1))
                sum += 2 * (a + c);
        }
    }
    printf("Ans = %d\n", sum);
}

핵심 아이디어

1. 피타고라스 삼각형 생성:
• m과 n을 사용하여 피타고라스 삼각형의 세 변을 생성합니다:
\[ a = \frac{m^2 - n^2}{2}, \quad b = m \cdot n, \quad c = \frac{m^2 + n^2}{2} \]

• 이 식은 피타고라스 삼각형의 생성 공식에서 \(m, n\)이 짝수인 경우를 제외한 특별한 형태입니다.

2. 홀수 m과 n:
• m과 n은 모두 홀수로 제한합니다.
• m과 n이 서로소가 아닐 경우 삼각형을 생성하지 않도록 필터링합니다.

3. 거의 정삼각형 조건:
• 생성된 삼각형에서 \(c\) 가 \( 2b \pm 1 \) 또는  \( 2a \pm 1 \)을 만족하는 경우만 유효합니다.

4. 둘레 조건:
• 삼각형의 둘레 \( 2 \times (b + c) \) 또는 \( 2 \times (a + c) \)가 LIMIT를 초과하지 않는지 확인합니다.

5. 둘레 합산:
• 조건을 만족하면 삼각형의 둘레를 총합 sum에 추가합니다.

4. 메인 함수
• 프로그램 시작 시 clock() 함수를 호출하여 시작 시간을 기록합니다.
• solve1() 함수를 호출하여 문제를 해결합니다.
• 종료 시, 프로그램의 실행 시간을 출력합니다.

성능 및 최적화
• 시간 복잡도: 
• 외부 루프: \( O(\sqrt{\text{LIMIT}}) \) (\(m^2\)의 증가 속도)
• 내부 루프: \( O(\sqrt{m}) \)
• 전체: 약 \( O(\sqrt{\text{LIMIT}} \cdot \sqrt{\text{LIMIT}}) = O(\text{LIMIT}) \)
• 최적화:
• \( gcd(m, n) > 1 \) 조건으로 불필요한 계산을 줄임.
• 피타고라스 삼각형의 대칭성과 홀수 특성을 사용하여 검색 범위를 좁힘.