[백준 1564번] 팩토리얼5: 정식 풀이

문제 링크

https://www.acmicpc.net/problem/1564

 

문제 요약

\(N\)이 주어졌을 때, \(N!\)의 마지막 0이 아닌 5자리 수를 출력하는 문제이다.

 

예를 들어, \(N\)이 10인 경우 \(10!\)은 3628800이며, 마지막 0이 아닌 5자리 숫자는 36288이 된다.

 

문제 풀이

BigInt와 같은 큰 수 자료형을 사용해 팩토리얼을 직접 계산하기 위해서는 많은 시간과 공간 복잡도가 필요하다. 따라서 더 효율적인 방법이 필요하다.

 

얼핏 보면 팩토리얼의 마지막 다섯 자리만 유지하면 될 것 같지만, 팩토리얼 값의 끝에 붙는 0, 즉 트레일링 제로를 제거하고 출력해야 하기 때문에 단순히 마지막 다섯 자리만 유지하는 것으로는 문제를 해결할 수 없다.

 

핵심은 트레일링 제로가 언제 생기는지 파악하는 것이다. 팩토리얼 값의 트레일링 제로는 2와 5의 인수 개수에 의해 결정된다. 곱셈 과정에서 2와 5가 짝을 이루면 10이 되고, 이는 곧 끝에 오는 0이 하나 생기는 것을 의미하기 때문이다. 따라서 팩토리얼을 계산할 때 각 수에서 2와 5의 인수를 제거하여 트레일링 제로를 없앨 수 있다. 그러나 팩토리얼에서 2의 인수는 5의 인수보다 항상 같거나 더 많으므로, 제거한 5의 인수 개수보다 초과된 2의 인수는 최종 결과에 다시 곱해주어야 한다.

 

마지막으로 다섯 자리를 출력할 때 앞에 0을 채워 출력하면 문제를 해결할 수 있다.

 

소스 코드

#include <stdio.h>

long long n;
const long long MOD = 1e5;

int main() {
    scanf("%lld", &n);
    
    long long ans = 1;
    int cnt2 = 0, cnt5 = 0;
    
    for (long long i = 2 ; i <= n ; ++i) {
        long long num = i;
        
        // 2의 인수를 제거
        while (num % 2 == 0) {
            cnt2 += 1;
            num /= 2;
        }
        
        // 5의 인수 제거
        while (num % 5 == 0) {
            cnt5 += 1;
            num /= 5;
        }
        
        ans = (ans * num) % MOD;
    }
    
    int extra2s = cnt2 - cnt5;
    
    // 트레일링 제로를 만들지 않는 2의 인수를 다시 곱함
    for (int i = 0 ; i < extra2s ; ++i){
        ans = (ans * 2) % MOD;
    }
    
    printf("%05lld\n", ans);
}