C++로 팩토리얼(n!)의 자릿수 합 구하기

숫자 n이 주어졌을 때, n!(팩토리얼)의 각 자릿수를 모두 더한 값을 구하는 것이 이 글의 목표입니다. 예를 들어 n = 5라면 5! = 120이므로, 자릿수의 합은 1 + 2 + 0 = 3이 됩니다.

문제 접근 방법

팩토리얼은 n이 조금만 커져도 기본 정수형(int, long long)의 표현 범위를 훌쩍 넘어섭니다. 따라서 일반적인 자료형으로는 계산 자체가 불가능하며, 큰 수 곱셈을 직접 구현해야 합니다.

여기서는 벡터(vector)를 활용합니다. 벡터의 각 원소에 팩토리얼 결과의 한 자릿수씩을 저장하고, 1부터 n까지의 수를 차례대로 곱해 나가는 방식입니다. 곱셈 과정에서 발생하는 올림수(carry)도 반드시 처리해야 정확한 결과를 얻을 수 있습니다.

알고리즘 단계

1. 자릿수를 저장할 벡터를 생성하고 1로 초기화합니다.
2. 1부터 n까지 각 숫자 i에 대해 벡터 전체에 i를 곱합니다. 이때 올림수를 계산해 다음 자릿수로 넘기며, 남은 올림수는 벡터 뒤에 추가합니다.
3. 모든 곱셈이 끝나면 벡터에 저장된 각 자릿수를 합산하여 반환합니다.

예제 코드

#include<iostream>
#include<vector>
using namespace std;

// 벡터에 저장된 큰 수에 x를 곱하는 함수
void vectorMultiply(vector<int> &v, int x) {
    int carry = 0, res;
    int size = v.size();
    for (int i = 0 ; i < size ; i++) {
        res = carry + v[i] * x;   // 현재 자릿수 계산
        v[i] = res % 10;          // 1의 자리만 저장
        carry = res / 10;         // 나머지는 올림수로
    }
    while (carry != 0) {          // 남은 올림수 처리
        v.push_back(carry % 10);
        carry /= 10;
    }
}

// n!의 자릿수 합을 구하는 함수
int digitSumOfFact(int n) {
    vector<int> v;
    v.push_back(1);               // 1로 초기화
    for (int i = 1; i <= n; i++)
        vectorMultiply(v, i);     // 1부터 n까지 곱하기
    int sum = 0;
    int size = v.size();
    for (int i = 0 ; i < size ; i++)
        sum += v[i];              // 모든 자릿수 합산
    return sum;
}

int main() {
    int n = 40;
    cout << "Digit sum of " << n << "! is: " << digitSumOfFact(n);
}

실행 결과

Digit sum of 40! is: 189

40!은 815915283247897734345611269596115894272000000000으로 총 48자리의 거대한 수이지만, 위 코드는 이를 문제없이 처리하며 자릿수의 합인 189를 정확히 출력합니다.

복잡도 분석

결과값의 자릿수를 d라고 할 때, 각 곱셈마다 벡터 전체를 순회하므로 시간 복잡도는 O(n × d)입니다. 공간 복잡도는 자릿수를 저장하는 벡터 크기만큼, 즉 O(d)입니다. 이 방식은 임의 정밀도(big integer) 연산을 지원하지 않는 환경에서도 손쉽게 큰 수의 팩토리얼을 다룰 수 있다는 장점이 있습니다.