[C/C++] 프로젝트 오일러 #91 Right Triangles with Integer Coordinates(전체 탐색)

Project Euler #91 문제는 좌표 평면에서 원점을 포함하여 세 점을 선택해 직각삼각형을 구성하는 경우의 수를 찾는 문제입니다. 문제의 주요 요구 사항은 다음과 같습니다:
1. 평면의 오른쪽 위에 있는 정사각형 영역(예를 들어, 크기  내의 점)을 대상으로 합니다.
2. 직각 삼각형의 세 꼭짓점 중 하나는 항상 원점(0,0)에 고정됩니다.
3. 나머지 두 점을 선택해 직각이 될 수 있는 경우를 찾습니다.
4. 삼각형의 직각은 두 변이 x축 또는 y축과 평행한 경우로 한정됩니다.

이 문제는 가능한 모든 점 조합을 조사하여 직각 조건을 만족하는 경우를 계산해야 하므로, 효율적인 알고리즘과 중복을 방지하는 로직이 필요합니다.

 

A wide horizontal illustration of a 50x50 coordinate grid with right triangles

 

제가 작성한 소스는 다음과 같습니다.

//------------------------------------------------
//    Project Euler #91 - Right Triangles with Integer Coordinates
//        - by Aubrey Choi
//        - created at 2015-04-12
//------------------------------------------------
#include <stdio.h>

#define    LIMIT    50

int main()
{
    int x1, y1, x2, y2;
    int count = LIMIT*LIMIT*3;

    for( x1 = 1 ; x1 <= LIMIT ; x1++ )
    {
        for( y1 = 1 ; y1 <= LIMIT ; y1++ )
        {
            x2 = y1; y2 = x1;
            while( y2 ) { int t = y2; y2 = x2%y2; x2 = t; }
            y2 = x1/x2; x2 = -y1/x2;
            for( int i = 1 ; ; i++, count++ )
                if( x1+x2*i > LIMIT || y1+y2*i > LIMIT || 
                    x1+x2*i < 0 || y1+y2*i < 0 ) break;
            for( int i = 1 ; ; i++, count++ )
                if( x1-x2*i > LIMIT || y1-y2*i > LIMIT || 
                    x1-x2*i < 0 || y1-y2*i < 0 ) break;
        }
    }
    printf("ans = %d\n", count);
}

 

 

\(50 \times 50\) 범위 내에서 원점을 포함하는 직각삼각형을 찾는 프로그램입니다. 코드의 주요 로직을 설명하겠습니다.

코드 설명

1. 상수 선언과 초기화:

#define LIMIT 50

문제의 제한에 맞춰 LIMIT을 50으로 정의합니다. 이는  범위에서 점을 선택하기 위한 한계를 설정하는 역할을 합니다.

2. 초기 카운트 설정:

int count = LIMIT*LIMIT*3;

count는 초기값으로 LIMIT * LIMIT * 3을 가집니다. 이 초기값은 x축과 y축에 평행한 직각삼각형의 경우(원점에서 x축 또는 y축 상에 위치한 삼각형)와 같은 기본 경우를 미리 포함한 것입니다.

3. 이중 for 루프:

for( x1 = 1 ; x1 <= LIMIT ; x1++ )
{
    for( y1 = 1 ; y1 <= LIMIT ; y1++ )
    {
        ...
    }
}

x1, y1은 원점이 아닌 점 (x1, y1)을 선택하기 위해 1부터 LIMIT까지 순회합니다.

4. 직각 삼각형의 성립 조건 계산:

x2 = y1; y2 = x1;
while( y2 ) { int t = y2; y2 = x2 % y2; x2 = t; }
y2 = x1 / x2; x2 = -y1 / x2;

여기에서, 직각을 이루기 위한 벡터를 생성합니다. 선택한 두 점이 (0,0)을 기준으로 직각을 이루도록 좌표 변환을 수행합니다. 이 과정에서 두 벡터가 수직 관계를 만족하도록 x2, y2를 조정합니다.

5. 첫 번째 반복문:

for( int i = 1 ; ; i++, count++ )
    if( x1 + x2 * i > LIMIT || y1 + y2 * i > LIMIT || 
        x1 + x2 * i < 0 || y1 + y2 * i < 0 ) break;

이 루프는 \((x_1, y_1)\)를 기준으로 직각을 이루는 점을 찾기 위해 반복합니다. LIMIT 범위를 벗어나면 루프를 중단하고 카운트를 증가시킵니다.

6. 두 번째 반복문:

for( int i = 1 ; ; i++, count++ )
    if( x1 - x2 * i > LIMIT || y1 - y2 * i > LIMIT || 
        x1 - x2 * i < 0 || y1 - y2 * i < 0 ) break;

이 반복문은 반대 방향으로 이동하며 직각삼각형을 찾는 역할을 합니다.

7. 결과 출력:

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

최종적으로 계산된 직각삼각형의 수를 출력합니다.

핵심 아이디어

• (0, 0)을 고정점으로 두고 (x1, y1), (x2, y2) 두 점을 선택해 두 변이 수직을 이루는지 확인합니다.
• 유클리드 호제법을 사용해 (x1, y1)과 직각이 되는 점의 벡터 방향을 찾아내어 범위 내 가능한 모든 점을 계산합니다.

요약

이 코드는 좌표 평면에서 원점과 두 점을 선택하여 직각삼각형을 구성할 수 있는 모든 경우를 효율적으로 계산합니다.