#58 문제도 난이도는 5% 문제입니다.


문제 자체는 복잡해 보여도 사실 푸는데 전혀 어려움이 없는 문제예요.



문제는 1부터 차례대로 나선형으로 수들을 배치하게 되면, 대각선쪽에는 홀수가 항상 배치되게 됩니다.  그럴 경우, 대각선에 있는 홀수 중 소수의 비율이 얼마일것인가가 이 문제를 푸는데 중요한 부분입니다.


이 문제는 소수의 비율이 10% 미만으로 떨어질 때, 한 변에 위치하는 수들의 갯수를 답하라는 것입니다.


배치하는 방법이 일정하기 때문에, 대각선에 위치한 숫자들의 순열만 파악하면 됩니다.


일단 첫번째 대각선(가장 작은 수)의 수열은 다음과 같이 표현할 수 있습니다.  s를 한변 길이의 절반이라고 할 때(즉, 1이 위치한 s는 0, 그 다음은 1, 그 다음은 2.. ),



이 것을 이용하여, 다음 수는 2s, 4s, 6s 만큼 더해주면 되겠죠.


이것을 단순하게 프로그램하면 아래와 같습니다.


void solve1()
{
    int64_t s, pcount = 0;
    for( s = 1 ;  ; s++ )
    {
        int64_t f = 4*s*s - 2*s + 1;
        if( isPrime(f) ) pcount++;
        if( isPrime(f+2*s) ) pcount++;
        if( isPrime(f+4*s) ) pcount++;
        if( isPrime(f+6*s) ) pcount++;
        if( pcount*10 < s*4+1 ) break;
    }
    printf("Ans = %I64d\n", s*2+1);
}


저작자 표시 비영리 변경 금지
신고



이번 문제는 수학 문제인 듯 보이지만, 그냥 단순 계산 문제입니다.

프로젝트 오일러 사이트 난이도 평가 5% 문제네요.



문제의 내용은 2의 제곱근을 구할 때, 연분수 전개를 할 수가 있습니다.  연분수 전개에 관련해서는 펠의 방정식(http://sdev.tistory.com/213) 글을 참조하세요.




와 같이 2의 제곱근을 표시할 수 있습니다.


이 문제에서는 이것이 중요한 것이 아니고, 이 연분수 전개를 할 때, 분수로 표현하게 되면, 분모와 분자가 모두 정수가 되는데, 분자의 정수부가 분보의 정수부보다 자릿수가 많은 것이 몇개가 있는 가가 문제입니다.


연분수 전개를 분수로 만들면 되는 것이지만, 연분수 전개 자체가 상당히 큰 자릿수가 나옵니다.  물론 double 형을 이용해서 근사치로 계산해도 되겠지만, 실제 double을 이용해서 계산하면, 이 문제의 답이 틀려지게 됩니다.  그만큼 예민해서, 어쩔 수 없이 BigInt를 이용해서 풀어야 합니다.


BigInt를 이용해서 푸는 것은 사실 C/C++ 언어보다는 Python과 같이 BigInt 라이브러리가 기본 제공되는 것을 이용하는 것이 편합니다.


저는 제가 직접 만든 BigInt 라이브러리를 이용했습니다.  


#include <stdio.h>
#include <time.h>
#include "NxBigInt.h"

void solve1()
{
    NxBigInt d = 2, n = 3, d1 = 1, n1 = 1;
    int count = 0;
    for( int i = 2 ; i <= 1000 ; i++ )
    {
        NxBigInt t;
        t = 2*d+d1; d1 = d; d = t;
        t = 2*n+n1; n1 = n; n = t;
        uint8_t s[1000];
        int l1 = d.ConvertToArrayLE(s, 1000);
        int l2 = n.ConvertToArrayLE(s, 1000);
        if( l2 > l1 ) count++;
    }
    printf("Ans = %d\n", count);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

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


python에 비해서 C/C++로 제가 효율이 그렇게 훌륭하다고 생각치는 않지만, 2~3배 빠르게 수행이 되었습니다.  인터넷에서 BigInt 라이브러리를 찾으셔서 C/C++에 적용해도 되고요.  


알고리즘 자체는 그다지 어렵지는 않습니다.


저작자 표시 비영리 변경 금지
신고



이 문제는 난이도 5% 문제이지만, BigInt 모듈이 없는 언어 사용자는 해당 모듈을 구해야 하는 어려움이 있습니다.  파이썬 등을 이용하면 간단하게 해결할 수 있습니다.



문제는 간단합니다.  a, b < 100 안에서 a의 b제곱한 결과를 10진수로 표현할 때, 모든 자릿수의 합 중 최대값을 찾으라는 것입니다.  최소값은 1인 것은 당연하고요.


좀 더 좋은 알고리즘을 찾는다는 것은 어려울 것 같습니다.  그냥 무식한 방법으로 풀어보았습니다.



#include <stdio.h>
#include <time.h>
#include "NxBigInt.h"

void solve1()
{
    int v = 9, a, b;

    for( int i = 2 ; i < 100 ; i++ )
    {
        NxBigInt m = i;
        for( int j = 2 ; j < 100 ; j++ )
        {
            m *= i;
            uint8_t s[1000];
            int len = m.ConvertToArrayLE(s, 1000);
            int sum = 0;
            for( int k = 0 ; k < len ; k++ )
                sum += s[k];
            if( sum > v ) { v = sum; a = i; b = j; }
        }
    }
    printf("Ans = %d, (a = %d, b = %d)\n", v, a, b);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

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


저작자 표시 비영리 변경 금지
신고