[C/C++] 프로젝트 오일러 #86 Cuboid Route(Brute Force)

난이도는 35%의 문제이지만, 단순 방법으로 처리하면 그래도 적당한 시간에 해답을 찾을 수 있습니다.

 

cuboid route

 

문제는 각 모서리의 길이가 정수인 직육면체의 대척점 길이가 정수가 되는 경우를 찾는 것이죠. \(W \times H \times D\) 형태에서 대척점의 길이는 \( \sqrt{ W^2 + H^2 + D^2 } \)이 됩니다. 이것이 정수가 되기 위해서는 \( W^2 + H^2 + D^2 \)이 제곱수여야 합니다. 수학적인 방법도 존재하겠죠. 피타고라스 수를 연결하면 될 듯 합니다. 3-4-5 와 5-12-13 은 연결이 됩니다. 즉, \(3^2 + 4^2 + 12^2\)은 제곱수가 될 수 있는 것이죠.

 

문제의 출처는 다음과 같습니다.

https://projecteuler.net/problem=86

 

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #86 - Cuboid Route
//        - by Aubrey Choi
//        - created at 2015-10-15
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

#define    LIMIT    1000000

void solve1()
{
    int count = 0, n;
    for( n = 3 ; count < LIMIT ; n++ )
    {
        for( int a = 1 ; a < n ; a++ )
        {
            int min, t;
            int s = a+n;
            min = s*s+n*n;
            s = n+n;
            t = s*s+a*a;
            if( min > t ) min = t;
            int r = sqrt((double)min);
            if( r*r == min ) count++;
        }
        for( int a = 1 ; a < n ; a++ )
        {
            for( int b = a ; b < n ; b++ )
            {
                int min, t;
                int s = a+b;
                min = s*s+n*n;
                s = a+n;
                t = s*s+b*b;
                if( min > t ) min = t;
                s = b+n;
                t = s*s+a*a;
                if( min > t ) min = t;
                int r = sqrt((double)min);
                if( r*r == min ) count++;
            }
        }
    }
    printf("Ans = %d (%d)\n", n-1, count);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

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

 

이 코드는 특정 수학적 조건을 만족하는 경우를 계산하는 프로그램입니다. 전체적으로 두 개의 반복문을 통해 숫자들의 조합을 계산하고, 그 조합에 대해 조건을 만족하는지 확인하며, 목표에 도달하면 프로그램이 종료됩니다.

코드의 주요 흐름을 설명하자면 다음과 같습니다.

주요 정의:

•    LIMIT: 1,000,000으로 설정된 목표값입니다. 특정 수학적 조건을 만족하는 경우의 수가 이 값에 도달할 때까지 계산이 진행됩니다.

solve1 함수:

이 함수는 핵심 계산을 수행합니다. 각 단계별 설명은 다음과 같습니다.

1.    변수 선언:
•    count: 조건을 만족하는 경우의 수를 저장하는 변수입니다.
•    n: 특정 계산에 사용되는 값으로, 매번 증가합니다.
2.    바깥쪽 루프 (for n = 3; count < LIMIT; n++):
•    n 값이 증가하면서 LIMIT을 만족할 때까지 계속됩니다.
3.    첫 번째 내부 루프 (for a = 1; a < n; a++):
•    a 값이 n보다 작은 값을 가지며, 각 a에 대해 아래 계산을 진행합니다.
4.    수학적 조건 계산:
•    s와 t는 다양한 조합으로 계산된 두 수의 합을 나타냅니다.
•    min: 두 수의 제곱합을 구하고, 그중 최소값을 저장합니다.
•    r: 최소 제곱합에서 제곱근을 계산하고, 다시 제곱했을 때 원래 값과 같은지 확인합니다. 즉, 정수 제곱근인지 검사하는 과정입니다.

이 조건을 만족하면 count를 증가시킵니다.
5. 두 번째 내부 루프 (for b = a; b < n; b++):
• 두 번째 내부 루프에서는 a와 b의 조합을 통해 동일한 조건을 만족하는지 계산합니다. 이때 a와 b는 서로 다른 값일 수 있습니다.
6. 조건 만족 시 카운트 증가:
• 정수 제곱근을 만족하는 경우 count가 증가합니다.

main 함수:

•    프로그램 실행 시간을 측정합니다.
•    solve1 함수가 호출되어 계산을 수행한 후, 걸린 시간을 출력합니다.

코드의 목표:

프로그램의 목표는 주어진 수학적 조건(제곱수 조건)을 만족하는 경우의 수가 LIMIT에 도달하는 첫 번째 n 값을 찾는 것입니다. 프로그램이 이 목표에 도달하면, 해당 n 값과 조건을 만족한 경우의 수를 출력하고 종료됩니다.

요약:

이 코드는 수학적 조건(제곱수 관계)을 만족하는 수의 조합을 찾아 카운트하고, 그 카운트가 1,000,000에 도달할 때까지 반복하는 알고리즘입니다.