[BOJ 2553 // C++] 마지막 팩토리얼 수

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2553번 문제인 마지막 팩토리얼 수이다.
문제는 아래 링크를 확인하자.

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

2553번: 마지막 팩토리얼 수

N이 많은 5를 인수로 갖고 있다면 (N-1)!에 N을 곱해 N!을 구할 때 N의 5의 인수개수만큼 다음 팩토리얼값에는 0이 늘어나게 된다. (2의 인수 개수가 항상 더 많다는 점을 관찰하자.)

 

20000 이하에서 자연수가 인수로 가질 수 있는 5의 개수의 최댓값은 6이다. 따라서 주어지는 수의 마지막 12자리만을 저장한다면 문제를 간단히 해결할 수 있다. 64비트 정수 자료형을 이용한다면 오버플로우 없이 계산 과정의 모든 연산들을 해낼 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll ans = 1;
	ll N; cin >> N;
	for (ll i = 1; i <= N; i++) {
		ans *= i;
		while (ans % 10 == 0) ans /= 10;
		ans %= 1000000000000LL;
	}

	cout << ans % 10;
}