프로젝트 오일러 #62 세제곱수 순열

이번 문제는 난이도 15% 문제네요.

 

저는 의외로 쉽게 풀었습니다.  (단순무식법으로요.)

 

 

서로 다른 세제곱수 5개가 같은 숫자들로 이루어진 경우 그 중 가장 작은 수를 구하라는 문제입니다.

 

사실 이 문제를 정석적으로 푼다면, 정확하게 5개가 나오는지 검사해야 하지만, 저는 그것까지는 검사하지 않았습니다.

 

또한 같은 숫자가 4개 이상 나오는 것도 배제했습니다.  사실 그러면 안 되지만, 배열에다가 데이터를 저장하는 방식을 이용하다보니, 같은 숫자가 4개 이상 나오면 안 되어서요.  해시를 쓰면 좀 더 나으려나요.  그러면 자릿수가 6자리인것, 7자리인것, .. 형태로 정확하게 5개가 나오면서, 같은 숫자가 4개 이상 나오는 것도 허용할 수 있었을텐데요.  그치만 복잡한 자료구조 쓰는 것을 귀찮아해서요.  (아무래도 기본적으로 STL이나 제공되는 자료구조가 없다면 잘 안 쓰게됩니다.)

 

아래는 제가 작성한 프로그램입니다.

 

 

#include <stdio.h>
#include <time.h>
#include <stdint.h>

int index(int64_t n)
{
    int cnt[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    while( n )
    {
        cnt[n%10]++;
        n /= 10;
    }
    int idx = 0;
    for( int i = 0 ; i < 10 ; i++ )
    {
        if( cnt[i] >= 4 ) return 0;
        idx <<= 2;
        idx |= cnt[i];
    }
    return idx;
}

void solve1()
{
    static int count[1<<20], value[1<<20];

    for( int i = 300 ; ; i++ )
    {
        int64_t cube = (int64_t)i*i*i;
        int idx = index(cube);
        if( idx == 0 ) continue;
        if( count[idx] == 4 )
        {
            int64_t v = value[idx];
            printf("Ans = %lld(%lld)\n", v*v*v, v);
            break;
        }
        if( count[idx] == 0 ) value[idx] = i;
        count[idx]++;
    }
}