정수가 하나 주어졌을 때, 해당 숫자가 각 자릿수의 계승(팩토리얼) 값들의 합을 나눌 수 있는지 확인해야 합니다. 예를 들어 숫자가 19라고 가정해 보겠습니다. 각 자릿수 계승의 합은 (1! + 9!) = 362881이며, 이 값은 19로 나누어 떨어지므로 조건을 만족합니다.
이 문제를 해결하는 방법은 간단합니다. 먼저 주어진 숫자를 임시 변수에 저장한 후, 각 자릿수를 추출하여 그 계승 값을 구하고 모두 더합니다. 마지막으로 이 합이 원래 숫자로 나누어 떨어지면 true를 반환하고, 그렇지 않으면 false를 반환하면 됩니다.
알고리즘 단계
- 원래 숫자를 임시 변수에 저장합니다.
- 나머지 연산자(%)를 사용해 숫자의 각 자릿수를 추출합니다.
- 각 자릿수의 계승을 계산하여 합계에 더합니다.
- 합계가 원래 숫자로 나누어 떨어지는지 확인합니다.
- 나누어 떨어지면 true, 아니면 false를 반환합니다.
예제 코드
#include <iostream>
using namespace std;
int factorial(int n){
if(n == 1 || n == 0)
return 1;
return factorial(n - 1) * n;
}
bool isDigitsFactDivByNumber(int num){
int temp = num;
int sum = 0;
while(num){
int digit = num % 10;
sum += factorial(digit);
num /= 10;
}
if(sum % temp == 0){
return true;
}
return false;
}
int main() {
int number = 19;
if (isDigitsFactDivByNumber(number))
cout << "Yes, the number can divide the sum of factorial of digits.";
else
cout << "No, the number can not divide the sum of factorial of digits.";
}출력 결과
Yes, the number can divide the sum of factorial of digits.
위 코드에서 factorial() 함수는 재귀 호출 방식으로 계승을 계산하며, 0과 1의 계승은 1로 처리합니다. isDigitsFactDivByNumber() 함수는 while 루프와 나머지 연산자를 활용해 각 자릿수를 하나씩 추출하고, 해당 자릿수의 계승 값을 누적하여 합계를 구합니다. 이 알고리즘의 시간 복잡도는 숫자의 자릿수에 비례하므로 매우 효율적으로 동작합니다.