[C/C++] 프로젝트 오일러 #34 : 자릿수의 팩토리얼 합(구현)

이번 문제는 각각의 자릿수의 팩토리얼 합이 자신이 되는 숫자를 찾는 것입니다.

 

예를 들어서 145란 숫자는,

 

\[1! + 4! + 5! = 1 + 24 + 120 = 145\]

 

가 됩니다.  이번 문제는 이와 비슷한 숫자들의 합을 구하는 것입니다.

 

이제 프로젝트 오일러를 이정도까지 진행하셨다면, 십진수의 자릿수를 빼는 것에는 다들 어느정도 경험이 있을 것이라 생각합니다.

 

제 경우에는 각 자릿수의 팩토리얼 값을 미리 저장해서 사용했습니다.

9! = 362880 이므로, 대충 6자릿수자일거라고 생각하면 됩니다.  그래서 숫자범위를 그렇게 정했습니다.

 

Digit Factorial Calculation Visualization

 

제가 작성한 프로그램은 다음과 같습니다.

//------------------------------------------------
//    Project Euler #34 - Digit Factorials
//        - by Aubrey Choi
//        - created at 2015-03-20
//------------------------------------------------
#include <stdio.h>

int main()
{
    int facts[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 36280 };

    int sum = 0;
    for( int i = 10 ; i < facts[9]*6 ; i++ )
    {
        int ss = 0;
        for( int k = i ; k ; ss += facts[k%10], k /= 10 ) ;
        if( ss == i ) sum += i;
    }
    printf("ans = %d\n", sum);
}

 

이 프로그램은 Project Euler의 문제 34인 “Digit Factorials” 문제를 해결하기 위한 코드입니다. 이 문제는 “각 자리 숫자의 팩토리얼 합이 자기 자신이 되는 모든 수를 구하라”는 문제입니다. 이 프로그램의 소스를 단계별로 설명해 보겠습니다.

코드 설명

1. 팩토리얼 배열 초기화

int facts[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };

facts 배열은 0부터 9까지의 각 숫자에 대한 팩토리얼 값을 저장합니다. 예를 들어, facts[5]는 5! (5 팩토리얼)인 120입니다.

2. 주된 변수 초기화

int sum = 0;

sum 변수는 조건을 만족하는 모든 숫자를 합산하기 위한 변수입니다.

3. 조건을 만족하는 숫자 찾기

for( int i = 10 ; i < facts[9]*6 ; i++ )

이 루프는 10부터 시작하여 6자리 숫자까지 반복합니다. facts[9]*6은 상한선을 설정하기 위한 값입니다. 9! * 6은 약 217728이며, 6자리의 각 자리 숫자가 모두 9일 때 팩토리얼의 합을 초과하지 않게끔 상한선을 설정한 것입니다.

4. 각 자리 숫자의 팩토리얼 합 계산

int ss = 0;
for( int k = i ; k ; ss += facts[k%10], k /= 10 ) ;

여기서 k = i로 시작하여, k를 10으로 나눈 나머지를 통해 현재 i의 가장 오른쪽 자리 수를 구하고, 그 자리의 팩토리얼 값을 ss에 누적합니다. 그런 다음 k를 10으로 나누어 자릿수를 옮깁니다. 이 과정을 반복하면서 i의 모든 자리 숫자 팩토리얼 합을 계산합니다.

5. 결과 검증 및 합산

if( ss == i ) sum += i;

ss가 i와 같다면, i는 각 자리 숫자 팩토리얼의 합이 자기 자신과 같은 숫자라는 뜻이므로 sum에 i 값을 더합니다.

6. 결과 출력

printf("ans = %d\n", sum);

조건을 만족하는 모든 숫자를 더한 값인 sum을 출력합니다.

요약

이 프로그램은 facts 배열을 이용해 각 숫자의 팩토리얼 값을 참조하며, 10 이상에서 6자리까지의 숫자 중에서 각 자리 숫자의 팩토리얼 합이 자기 자신과 같은 숫자를 찾아 합산하여 최종 결과를 출력합니다.