#74 자릿수 팩토리얼 연결 고리

10진수의 수를 각각의 자릿수를 분해해서 재조합하다보면 재미있는 수를 얻을 수 있습니다.

예를 들어서 145라는 수를 분해해서 팩토리얼을 취한후 합해보면, \(145 \to 1! + 4! + 5! = 1+24+120=145\)라는 결과를 얻게 됩니다.  이와 같이 같은 수가 나올 수 있지만, 어떤 수는 위의 작업을 반복하다보면, 자신의 수가 되기도 하고 중간에 나왔던 수가 되어 싸이클을 반복할 수도 있습니다.  이 문제는 이러한 수들의 연결고리가 반복되기 전까지 얼마나 오래 가는가에 대한 문제입니다.

 

factorial

 

난이도 15% 정도로 구현에 어려움이 없는 문제입니다.

 

문제의 링크입니다.

https://projecteuler.net/problem=74

Problem 74 - Project Euler

 

10진수에서 자릿수가 가질 수 있는 수는 0부터 9까지 총 10가지이므로 팩토리얼은 미리 저장해놓고 그것을 사용합니다.  그러면 자릿수만 분리하면 됩니다.  이런 알고리즘 문제를 풀다보면, 자릿수만 분리하는 코드를 많이 사용하게 됩니다.

 

for(scanf("%d",&n);n;n/=10) printf("%d\n", n%10);

 

양수인 n이 입력되면, 낮은 자리부터 차례대로 자릿수를 출력해주는 코드입니다.  이를 이용해서 팩토리얼의 합을 구하는 것은 간단합니다.  시간이 오래 걸리는 작업은 오히려 60번까지 루프가 생기는지 검사하는 것입니다.  이에 대해서는 동적 프로그래밍 등을 통해서 해결할 수 있을겁니다.

 

동적 프로그래밍을 이용해서 문제를 풀어보면 약 502ms 정도가 나옵니다.  숫자가 큰 관계로 동적 프로그래밍을 위한 저장공간을 꽤 크게 잡아야 합니다.

 

제가 작성한 소스는 다음과 같습니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//  Project Euler #74 - Digit factorial chains
//    - by Aubrey Choi
//    - created at 2015-10-07
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdint.h>
#include <time.h>

int factsum(int n)
{
  static int fs[5000000];
  const int fact[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };

  if( fs[n] ) return fs[n];
  int sum = 0;
  while( n )
  {
    sum += fact[n%10];
    n /= 10;
  }
  return fs[n] = sum;
}

int getrepeat(int n)
{
  static char repeat[5000000];

  if( repeat[n] == 1 ) return 0;
  int s = factsum(n);
  repeat[n] = 1;
  int count = getrepeat(s)+1;
  repeat[n] = 0;
  return count;
}

void solve1()
{
  int count = 0;

  for( int i = 0 ; i < 1000000 ; i++ )
  {
    if( getrepeat(i) == 60 ) 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);
}