[C/C++] 프로젝트 오일러 #30 : 각 자릿수의 5제곱의 합

Project Euler 문제 #30은 각 자리의 숫자를 다섯 번째 거듭제곱한 값의 합이 자신과 같은 숫자들을 찾는 문제입니다. 문제에서는 한 자리 숫자는 조건을 만족할 수 없으므로 최소 두 자리 이상의 숫자부터 탐색해야 합니다.

이를 해결하기 위해, 특정 숫자의 각 자리 숫자를 다섯 번째 거듭제곱한 값들의 합을 계산하고, 이 합이 원래 숫자와 동일한 경우를 찾습니다. 조건을 만족하는 모든 숫자를 구한 후, 이 숫자들의 합을 계산하는 것이 문제의 목표입니다.

효율적인 계산을 위해 탐색 범위를 설정해야 하며, 숫자의 자리수가 증가함에 따라 다섯 번째 거듭제곱의 합이 해당 숫자를 초과하지 않는 범위를 고려하여 상한선을 정합니다. 이를 통해 필요한 계산을 제한하여 문제를 해결합니다.

 

문제 자체의 난이도는 그리 어렵지 않습니다.  프로젝트 오일러 사이트에서 책정된 난이도는 5%로, "매우 쉬움" 난이도입니다.

 

일단 5제곱을 계산하는 것은 반복된 작업이라서 배열을 이용해서 0~9까지의 5제곱을 구해서 적어놓았습니다.  이렇게 하니까 문제 자체가 깔끔해지네요.

 

시간도 상당히 적게 들고요.

또 고민했던 것이 얼마나 많은 숫자까지 연산할 것인가였죠.

 

9의 5승이 59049이니까요.  6자리 숫자(9라는 숫자가 2개만 있어도 6자리이니)까지 가능하겠죠.  좀 더 잘 짠다면, 반복연산하는 부분을 더 줄일 수 있을텐데요.

 

digit sum

 

소스를 첨부합니다.  제공된 소스는 참고용으로만 봐주세요.

//------------------------------------------------
//    Project Euler #30 - Digit Fifth Powers
//        - by Aubrey Choi
//        - created at 2015-02-04
//------------------------------------------------
#include <stdio.h>

int main()
{
    int sum = 0;
    const int v[10] = { 0, 1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049 };

    for( int i = 11 ; i <= 6*v[9]  ; i++ )
    {
        int q = i;
        int s = 0;
        while(q)
        {
            int r = q%10;
            s += v[r];
            q /= 10;
        }
        if( s == i ) 
        {
            sum += i;
            printf("%d\n", i);
        }
    }
    printf("Ans = %d\n", sum);
}

 

코드 설명
1. 상수 배열 v 선언
배열 v는 0부터 9까지의 숫자를 다섯 번째 거듭제곱한 값을 미리 계산해 저장한 것입니다.
예: v[2]는 \(2^5 = 32\), v[9]는 \(9^5 = 59049\)입니다.
이를 통해 반복적인 거듭제곱 계산을 피하고 실행 시간을 단축합니다.
2. 탐색 범위 설정
반복문은 i = 11부터 시작하여 \(6 \times v[9]\)까지 순회합니다.
\(6 \times v[9] = 354294\)는 6자리 숫자의 최댓값으로, 9의 5승을 6번 더한 값입니다. 이 값이 탐색 가능한 최대 숫자입니다.
3. 각 숫자에서 다섯 번째 거듭제곱의 합 계산
• q에 현재 숫자 i를 저장합니다.
• while 루프를 사용해 숫자의 각 자리 숫자를 추출(r = q % 10)하고, 해당 숫자의 다섯 번째 거듭제곱 값을 s에 누적합니다.
• q /= 10을 통해 자리수를 줄여가며 반복합니다.
4. 조건 만족 여부 확인
• 만약 다섯 번째 거듭제곱의 합 s가 원래 숫자 i와 같다면, 이 숫자를 출력하고, sum 변수에 더합니다.
5. 결과 출력
반복문이 종료되면 sum에 조건을 만족하는 모든 숫자의 합이 저장되며, 이를 출력합니다.

출력 결과
• 조건을 만족하는 숫자들이 출력됩니다.
• 마지막에 조건을 만족하는 숫자들의 합(Ans)이 출력됩니다.