C++로 N 팩토리얼 합의 마지막 두 자리 숫자 구하기

이 글에서는 1!부터 N!까지의 계승(팩토리얼) 합에서 일의 자리와 십의 자리, 즉 마지막 두 자리 숫자를 구하는 방법을 알아봅니다.

예를 들어 N = 4라고 가정해 보겠습니다. 그러면 1! + 2! + 3! + 4! = 1 + 2 + 6 + 24 = 33이 되고, 따라서 결과는 33입니다.

핵심 아이디어: 규칙성 찾기

계승 값을 자세히 관찰하면 중요한 규칙을 발견할 수 있습니다.

• N > 5인 모든 수의 계승은 항상 일의 자리가 0입니다. 따라서 5! 이후의 항들은 일의 자리에 더 이상 영향을 주지 않습니다.
• N ≥ 10인 모든 수의 계승은 마지막 두 자리가 모두 00입니다. 즉, 10!부터는 합의 마지막 두 자리에 아무런 변화도 주지 못합니다.

따라서 N이 10 이상이면 답은 항상 고정된 값이 됩니다. N = 1부터 10까지의 계승 값을 표로 정리하면 다음과 같습니다.

알고리즘 설계

위의 규칙을 활용하면 문제를 다음과 같이 간단하게 해결할 수 있습니다.

• N < 10인 경우: 1!부터 N!까지 직접 계산한 뒤 100으로 나눈 나머지를 반환합니다. → (1! + 2! + … + n!) mod 100
• N ≥ 10인 경우: 10! 이후의 항은 마지막 두 자리에 영향을 주지 않으므로, 미리 계산된 고정값 13(= (1! + 2! + … + 9!) mod 100)을 그대로 반환합니다.

이 방식을 사용하면 N이 아무리 커도 상수 시간 O(1)에 가깝게, 최대 9번의 곱셈만으로 답을 구할 수 있습니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int getTenAndUnitPlace(long long N) {
    if (N <= 10) {
        long long ans = 0, factorial = 1;
        for (int i = 1; i <= N; i++) {
            factorial = factorial * i;
            ans += factorial;
        }
        return ans % 100;
    }
    // N이 10보다 크면 마지막 두 자리는 항상 13
    return 13;
}

int main() {
    for (long long i = 1; i < 15; i++) {
        cout << "N = " << i << "일 때 계승 합의 마지막 두 자리 값: "
             << getTenAndUnitPlace(i) << endl;
    }
}

실행 결과

N = 1일 때 계승 합의 마지막 두 자리 값: 1
N = 2일 때 계승 합의 마지막 두 자리 값: 3
N = 3일 때 계승 합의 마지막 두 자리 값: 9
N = 4일 때 계승 합의 마지막 두 자리 값: 33
N = 5일 때 계승 합의 마지막 두 자리 값: 53
N = 6일 때 계승 합의 마지막 두 자리 값: 73
N = 7일 때 계승 합의 마지막 두 자리 값: 13
N = 8일 때 계승 합의 마지막 두 자리 값: 33
N = 9일 때 계승 합의 마지막 두 자리 값: 13
N = 10일 때 계승 합의 마지막 두 자리 값: 13
N = 11일 때 계승 합의 마지막 두 자리 값: 13
N = 12일 때 계승 합의 마지막 두 자리 값: 13
N = 13일 때 계승 합의 마지막 두 자리 값: 13
N = 14일 때 계승 합의 마지막 두 자리 값: 13

마무리

출력 결과에서 확인할 수 있듯이, N이 10 이상이 되면 계승 합의 마지막 두 자리는 항상 13으로 고정됩니다. 이처럼 큰 수의 계승을 직접 계산하지 않고도 수학적 규칙성을 파악하면 오버플로우 걱정 없이 매우 효율적으로 문제를 해결할 수 있습니다. 코딩 테스트에서 큰 수의 특정 자릿수를 묻는 유형의 문제에 널리 응용되는 기법이니 꼭 기억해 두시기 바랍니다.