프로젝트 오일러 #61 순환하는 n각수

이 문제는 60번에 이어서 연속으로 난이도 20% 문제이지만, 제 경우에는 그렇게 어렵지 않게 풀었던 문제입니다.

 

n각수 문제를 풀기 위해서는 n각수인 조건을 잘 검사하면 큰 무리가 없을 것이라 생각합니다.

 

 

이 문제는 두자릿수씩 겹치면서 순환하는 6개의 수가, 각각 3각수, 4각수, ..., 8각수가 되는 수열을 구하라는 것입니다.

 

3각수가 되는 4자리 수를 구한후, 뒤의 두자리수로 시작하는 4각수가 되는 수를 구하는 식으로 연결지어서 최종적으로 3각수의 첫두자리수로 끝나는 8각수를 만들면 됩니다.

 

제 경우에는 미리 n각수를 다 구한다음에, 해당수들이 순환하는지 검사하는 코드를 작성했습니다.  실제로 4자리 n각수가 많지는 않습니다.  모든 n각수는 2차식이기 때문에 상당히 빠르게 숫자가 커집니다.

 

 

#include <stdio.h>
#include <math.h>

int cyclic(int bitflag, int start, int end, int sum);
int polygonal[6][1000];
int pcount[6] = { 0, 0, 0, 0, 0, 0 };

int main()
{
    int pdiff[6] = { 1, 1, 1, 1, 1, 1 };
    int pdiff2[6] = { 1, 2, 3, 4, 5, 6 };

    for( int i = 0 ; i < 6 ; i++ )
    {
        int s = 0;
        for( int n = 0 ; ; n++, pdiff[i] += pdiff2[i] )
        {
            s += pdiff[i];
            if( s < 1000 ) continue;
            if( s >= 10000 ) break;
            if( s%100 < 10 ) continue;
            polygonal[i][pcount[i]++] = s;
        }
        printf("%d : %d\n", i, pcount[i]);
    }
    for( int i = 0 ; i < pcount[0] ; i++ )
    {
        int c = polygonal[0][i];
        int ans = cyclic(1, c%100, c/100, c);
        if( ans ) printf("Ans = %d\n", ans);
    }
}

int cyclic(int bitflag, int start, int end, int sum)
{
    if( bitflag == 0x3f )
    {
        if( start == end ) return sum;
        return 0;
    }
    for( int i = 1 ; i < 6 ; i++ )
    {
        if( (bitflag>>i)&1 ) continue;
        for( int j = 0 ; j < pcount[i] ; j++ )
        {
            int c = polygonal[i][j];
            if( c/100 == start )
            {
                int ans = cyclic(bitflag|(1<<i), c%100, end, sum+c);
                if( ans ) return ans;
            }
        }
    }
    return 0;
}