12. 프로젝트 오일러 #12 : 500개 초과 삼각수 구하기

이번 문제는 삼각수에 대한 것입니다.

간단한 중학수학 수준만 알고 있다면, 이 문제를 좀 빠르게 풀 수 있을 것이라 생각합니다.

1~n 까지의 합은 다음과 같은 식으로 구할 수 있습니다.

그 다음은 약수들의 갯수를 구하는 방법입니다.  예를 들어서 12의 약수의 갯수는 다음과 같이 계산할 수 있습니다.

이것만 알아도, 보다 쉽게 약수의 갯수를 구할 수 있습니다.

조금 더 나아간다면, n과 n+1은 서로소관계이므로,

을 적용할 수 있습니다.

그래서 n이 짝수인 경우와 홀수인 경우로 나누고, 동적 프로그래밍을 이용하면, 빠르게 원하는 답을 얻을 수 있습니다.  프로젝트 오일러 사이트에 가보면, 어떤분은 수십초가 걸렸다고 하는데요.  제 경우에는 노트북에 가상머신을 잡고 리눅스를 돌렸는데, time으로 실행시간을 검사하니 2밀리초 이내가 걸리네요.

#define NUM 500

int GetNumDivisors(int n);

int solve1()
{
    int n = NUM;
    int a, b;

    b = GetNumDivisors(n++/2);
    for( ; ; )
    {
        a = GetNumDivisors(n++);
        if( a*b > NUM ) break;
        b = GetNumDivisors(n++/2);
        if( a*b > NUM ) break;
    }

    printf("Ans = %d\n", (n-2)*(n-1)/2);
}

int GetNumDivisors(int n)
{
    int c = 1;
    int k;

    for( k = 0 ; !(n%2) ; k++ ) n /= 2;
    c = k+1;
    for( int p = 3 ; p*p <= n ; p+=2 )
    {
        for( k = 0 ; !(n%p) ; k++ ) n /= p;
        c *= k+1;
    }
    return c*((n > 1)+1);
}