[C/C++] 프로젝트 오일러 #99 Largest Exponential(수학)

문제는 여러 쌍의 숫자로 이루어진 데이터에서 각 쌍이 \(a^b\) 형태로 표현될 때, 가장 큰 값을 가지는 쌍의 위치를 찾는 것입니다. 여기서 a와 b는 양의 정수입니다.

예를 들어, 다음과 같은 쌍이 있다고 가정합니다:
1. \(2^{11}\)
2. \(3^7\)
3. \(6^3\)

각각의 값을 계산하면:
• \( 2^{11} = 2048 \)
• \( 3^7 = 2187 \)
• \( 6^3 = 216 \)

이 중에서 가장 큰 값은 2187이므로, 두 번째 쌍 (3, 7)이 답이 됩니다. 이 경우 결과는 2번째 줄을 나타냅니다.

문제가 간단하게 보여도 제곱해야 하는 수가 크면, 실제 값의 크기는 컴퓨터로 계산하기 힘듭니다.

 \( 632382^{518061} \gt 519432^{525806} \) 의 경우와 같이 밑수도 크고 지수도 큰 경우 대소 비교가 힘듭니다.

 

exponential

 

제가 작성한 코드입니다.

//------------------------------------------------
//    Project Euler #99 - Largest Exponential
//        - by Aubrey Choi
//        - created at 2015-10-25
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

#define    FILENAME    "0099.txt"

void solve1()
{
    FILE *fi = fopen(FILENAME, "r");
    int maxline = 0, maxbase, maxexp;
    double maxv = 0;
    for(int line = 1 ; ; line++)
    {
        char str[100];
        if( fgets(str, 100, fi) == NULL ) break;
        int base, expv;
        sscanf(str, "%d,%d", &base, &expv);
        double v = log10((double)base)*(double)expv;
        if( v > maxv ) { maxv = v; maxline = line; maxbase = base; maxexp = expv; }
        static int first = 1;
        if( first++ == 1 ) printf("%d, %d\n", base, expv);
    }
    fclose(fi);
    printf("Ans = %d(%d, %d)\n", maxline, maxbase, maxexp);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

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

 

이 코드는 로그 변환을 사용하여 매우 큰 숫자의 지수를 효율적으로 비교하는 방법을 구현하고 있습니다. 주어진 \( (a, b) \) 쌍에서 \( a^b \)의 값을 직접 계산하지 않고, 로그 함수를 활용해 비교 가능하도록 변환한 뒤 최대값을 찾는 방식입니다. 구체적으로, 다음의 수학적 아이디어를 사용합니다:

\[ \log_{10}(a^b) = b \cdot \log_{10}(a) \]


이를 통해 \( a^b \) 대신 \( b \cdot \log_{10}(a) \)를 계산하여 값의 크기를 비교할 수 있습니다. 이 기법은 \(a^b\) 를 직접 계산할 때 발생할 수 있는 오버플로우 문제를 방지하며, 효율적으로 결과를 도출할 수 있습니다.

1. 파일 열기

FILE *fi = fopen(FILENAME, "r");

• "0099.txt"라는 파일을 읽기 모드로 엽니다. 이 파일에는 문제에서 제공하는 (a, b) 쌍의 데이터가 들어있습니다.

2. 변수 초기화

int maxline = 0, maxbase, maxexp;
double maxv = 0;

• maxline: 가장 큰 값을 가진 쌍의 줄 번호를 저장.
• maxbase, maxexp: 가장 큰 값을 가진 (a, b) 쌍의 값.
• maxv: 최대 \( b \cdot \log_{10}(a) \)값을 저장.

3. 파일 데이터 읽기

for(int line = 1 ; ; line++) {
    char str[100];
    if( fgets(str, 100, fi) == NULL ) break;
    int base, expv;
    sscanf(str, "%d,%d", &base, &expv);
}

• fgets로 한 줄씩 데이터를 읽습니다. 파일 끝에 도달하면 반복문을 종료합니다.
• 읽은 문자열 str에서 sscanf를 사용해 (a, b) 값을 추출합니다.

4. 로그 값 계산 및 비교

double v = log10((double)base)*(double)expv;
if( v > maxv ) { 
    maxv = v; 
    maxline = line; 
    maxbase = base; 
    maxexp = expv; 
}

• 각 쌍에 대해 를 \( b \cdot \log_{10}(a) \) 계산합니다.
• 계산된 값이 현재 최대값 maxv보다 크면, maxv, 줄 번호(maxline)와 max (base, exp) 값들도 업데이트합니다.