프로젝트 오일러 #68 매직 오각 링

이 문제는 난이도 25%로 앞에 나열된 문제들에 비해서는 높은 편입니다.

 

매직 오각 링이라는 도형이 들어가는데, 이 도형만 잘 이해가 된다면 어려운 문제까지는 아닙니다.

 

매직 삼각 링

위 그림은 매직 삼각 링입니다.  매직 삼각 링은 6개의 숫자가 있는데, 여기에 1 부터 6까지의 숫자를 채워넣게 됩니다.

그런데 여기에는 규칙이 있습니다.  일직선상의 세개 숫자의 합이 모두 같아야 합니다.  위 그림에서는 각 숫자들의 합이 9로 동일합니다.

 

매직 오각 링

이 그림이 매직 오각 링이며, 여기서 구해야할 문제입니다.  이 매직 오각 링에 들어갈 숫자는 1 부터 10까지의 숫자입니다.  이 숫자들을 세개의 숫자씩 시계방향으로 쭉 나열하면 총 15개의 숫자가 나옵니다.  그런데 10이란 숫자가 있으니까, 이 숫자들을 모두 붙이면, 16자리 또는 17자리의 숫자열이 만들어집니다.  문제에서 요구하는 것은 16자리 숫자열 중에 가장 큰 숫자열을 계산하라는 것입니다.

 

문제에서 가장 큰 숫자열을 계산하라는 것이므로, 무조건 큰 숫자 위주로 우선 적용하도록 합니다.  그래서 처음 올바르게 나온 해가 답이 되도록 했습니다.  16자리여야 하기때문에 반드시 10은 외곽에 자리잡아야 합니다.  그래서 경우의 수가 좀 있습니다.  사실 10은 숫자 나열상으로는 가장 작은 수입니다.  1 은 다음수로 반드시 1보다 큰 수가 오지만, 10은 1 다음에 0이 오니까, 10이 앞으로 올 수록 손해인 수가 되겠죠.

 

여러 경우의 수를 적용해서 문제를 풀었고, 실제 답을 내는데 프로그램이 걸리는 시간은 2ms 이하입니다.

 

다음은 제가 작성했던 소스이며, 소스는 참고용으로만 봐주세요.

//----------------------------------------------------------------------------------------
//  Project Euler #68 - Magic 5-gon ring
//    - by Aubrey Choi
//    - created at 2015-10-01
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <time.h>
#include <math.h>

bool maxv(int s[], int k, char *res, int m)
{
  const int d[15] = { 0, 5, 6, 1, 6, 7, 2, 7, 8, 3, 8, 9, 4, 9, 5 };
  
  if( k == 10 )
  {
    char *p = res;
    for( int i = 0 ; i < 15 ; i++ )
    {
      if( s[d[i]] == 10 ) { *p++ = '1'; *p++ = '0'; }
      else *p++ = '0'+s[d[i]];
    }
    *p = 0;
    return true;
  }

  if( k < 5 )
  {
    const int v[4] = { 9, 8, 7, 10 };
    for( int i = 0 ; i < 4 ; i++ )
    {
      if( m&(1<<v[i]) ) continue;
      s[k] = v[i];
      if( maxv(s, k+1, res, m|(1<<v[i])) ) return true;
    }
    return false;
  }

  if( k == 5 )
  {
    s[5] = 5;
    return maxv(s, k+1, res, m|(1<<5));
  }

  for( int i = 5 ; i > 0 ; i-- )
  {
    if( m&(1<<i) ) continue;
    bool isGood = true;
    s[k] = i;
    int lastsum = s[d[0]]+s[d[1]]+s[d[2]];
    for( int j = 0 ; j < 5 ; j++ )
    {
      if( d[j*3+1] <= k && d[j*3+2] <= k )
      {
        int sum = s[d[j*3+0]]+s[d[j*3+1]]+s[d[j*3+2]];
        if( lastsum == 0 ) lastsum = sum;
        if( sum != lastsum ) { isGood = false; break; }
      }
    }
    if( isGood == false ) continue;
    if( maxv(s, k+1, res, m|(1<<i)) ) return true;
  }

  return false;
}

void solve1()
{
  int s[10] = { 6, }, m = (1<<6);
  char res[20] = "";

  maxv(s, 1, res, m);
  printf("Ans = %s\n", res);
}

int main()
{
  clock_t t;

  t = clock();

  solve1();

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