C++로 구현하는 듀드니 수(Dudeney Number) 판별 알고리즘

듀드니 수(Dudeney Number)란?

듀드니 수(Dudeney Number)는 수론(number theory)에서 정의되는 수학적 개념입니다. 어떤 자연수가 다른 자연수의 완전세제곱(perfect cube)과 같고, 원래 수의 각 자릿수 합과 세제곱근이 되는 수의 자릿수 합이 서로 동일할 때, 그 수를 듀드니 수라고 부릅니다(Wikipedia).

이 수는 영국의 퍼즐 제작자 헨리 듀드니(Henry Dudeney)에 의해 발견되었습니다. 듀드니 수의 수학적 정의는 다음과 같습니다.

대표적인 예로 512를 들 수 있습니다. 512 = 8³이며, 5 + 1 + 2 = 8로 세제곱근인 8과 자릿수 합이 정확히 일치합니다.

이번 글에서는 정수 n이 주어졌을 때, 주어진 수 n이 듀드니 수인지 아닌지를 판별하는 방법을 알아보겠습니다.

문제 이해를 위한 예시

입력: N = 17592

출력: No

설명:

주어진 수 17592는 듀드니 수가 아닙니다. 25³ = 15625, 26³ = 17576이므로 17592는 완전세제곱수조차 아니기 때문입니다.

해결 접근 방식

이 문제의 해결책은 듀드니 수의 기본 정의에서 출발합니다. 즉, 어떤 수의 세제곱근이 그 수의 자릿수 합과 같다면 그 수는 듀드니 수라는 성질을 활용합니다.

알고리즘

1단계: n이 완전세제곱수인지 확인합니다.

2단계: n이 완전세제곱수라면, n의 세제곱근이 n의 자릿수 합과 같은지 검사합니다.

• 같다면 → 해당 수는 듀드니 수입니다.
• 다르다면 → 해당 수는 듀드니 수가 아닙니다.

3단계: n이 완전세제곱수가 아니라면, 해당 수는 듀드니 수가 아닙니다.

C++ 코드 구현

위에서 설명한 알고리즘의 동작을 보여주는 C++ 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;

int calcDigitSum(int n){

    int digitSum = 0;
    int digitVal;
    while (n > 0) {
        digitVal = n % 10;
        digitSum += digitVal;
        n /= 10;
    }
    return digitSum;
    
}
int checkDudeney(int N) {
    
    int cubeRoot = int( round( cbrt(N) ) );
    
    if(pow(cubeRoot, 3.0) != N){
        return 0;
    }

    int sumOfDigit = calcDigitSum(N);
    
    if (cubeRoot != sumOfDigit)
        return 0;

    return 1;
}

int main() {
    int N = 104323;
    cout<<"The number "<<N;
    if (checkDudeney(N))
        cout<<" is a dudeney number.";
    else
        cout<<" is not a dudeney number.";
    return 0;
}

실행 결과

The number 104323 is not a dudeney number.

104323은 완전세제곱수가 아니므로 듀드니 수가 아니라는 결과가 출력됩니다. 이처럼 완전세제곱 여부 확인과 자릿수 합 비교, 두 단계만 거치면 손쉽게 듀드니 수를 판별할 수 있습니다.