C++를 사용해 N 팩토리얼 합의 일의 자릿수 구하기

문제 소개

이번 글에서는 C++를 사용해 1!부터 N!까지 팩토리얼의 합에서 일의 자리 숫자를 구하는 방법을 알아봅니다. 예를 들어 N = 3이라면 1! + 2! + 3! = 9가 되므로 결과값은 9이고, N = 4라면 1! + 2! + 3! + 4! = 33이 되어 일의 자리 숫자는 3입니다.

여기서 중요한 규칙성이 하나 있습니다. 5 이상 숫자의 팩토리얼은 항상 일의 자리가 0으로 끝납니다. 실제로 5! = 120, 6! = 720, 7! = 5040처럼 5!부터는 인수 2와 5가 반드시 함께 곱해지기 때문에 끝자리가 항상 0이 됩니다. 따라서 N이 5보다 큰 경우 해당 팩토리얼들은 합의 일의 자리에 아무런 영향을 주지 않습니다.

결론적으로 N이 4 이상이면 답은 항상 3으로 고정됩니다. 그렇기 때문에 복잡한 반복 연산 없이, 미리 계산해 둔 일의 자리 값 표(룩업 테이블)만으로도 상수 시간 O(1) 안에 정답을 구할 수 있습니다.

C++ 구현 코드

#include<iostream>
using namespace std;

int getUnitPlace(int n) {
    int placeVal[5] = {-1, 1, 3, 9, 3};
    if(n > 4){
        n = 4;
    }
    return placeVal[n];
}

int main() {
    for(int i = 1; i < 10; i++){
        cout << "N = " << i << "일 때 팩토리얼 합의 일의 자리 값: " << getUnitPlace(i) << endl;
    }
}

실행 결과

N = 1일 때 팩토리얼 합의 일의 자리 값: 1
N = 2일 때 팩토리얼 합의 일의 자리 값: 3
N = 3일 때 팩토리얼 합의 일의 자리 값: 9
N = 4일 때 팩토리얼 합의 일의 자리 값: 3
N = 5일 때 팩토리얼 합의 일의 자리 값: 3
N = 6일 때 팩토리얼 합의 일의 자리 값: 3
N = 7일 때 팩토리얼 합의 일의 자리 값: 3
N = 8일 때 팩토리얼 합의 일의 자리 값: 3
N = 9일 때 팩토리얼 합의 일의 자리 값: 3

마무리

이 문제는 팩토리얼의 성질, 즉 5!부터 끝자리가 0이 된다는 사실만 파악하면 매우 간단하게 해결할 수 있습니다. N이 아무리 커져도 배열 인덱스를 4까지만 참조하면 되므로, 시간 복잡도와 공간 복잡도가 모두 O(1)인 매우 효율적인 풀이가 됩니다.