[여덟번째 문제] 백준 / 2553 : 마지막 팩토리얼 수

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


// 일반적인 factorial 구하기에서 , 시간이 0.3초이므로
// 메모이제이션 활용,  구해진 숫자를 string으로 변환하여 
// 마지막이 0이면 앞으로 넘어오는식으로 구한다.
//

// 1! 1
// 2! 2
// 3! 6
// 4! 24
// 5! 120
// 6! 720
// 7! 5040
// 8! 40320
// 9! 362880
// 는 50!만해도 10의 64승이므로, 마지막숫자만 저장하는것이 맞는듯하다

long long int calfirst(long long int num) {
	while (num % 10 == 0) {
		num = num / 10;
	}
	long long int c_1 = num / 10000;
	num = num % 10000;
	long long int c_2 = num / 1000;
	num = num % 1000;
	long long int c_3 = num / 100;
	num = num % 100;
	long long int c_4 = num / 10;
	num= num %10;
	long long int c_5 = num;
	return(c_1 * 10000 + c_2 * 1000 + c_3 * 100 + c_4 * 10 + c_5);
}

int main() {
	int N;
	cin >> N;
	long long int c = 1;
	for (int i = 1; i <= N; i++) {
		c = calfirst(c * i);
		c= c % 10000000;
	}
	c = c % 10;
	cout << c;

	return 0;
}

주석을 보면 알 수 있겠지만, 메모이제이션을 써보려고 했는데 재귀로 함수를 실행하니까 3천번만에 스택이 터졌다.

그래서 급하게 반복문으로 틀었는데, 처음에는 뒤에 곱하는 수가 최대 2만이니까 , c = c % 100000 으로 다섯자리만 계속 곱해서 구하려고 했다.

그런데 45%에서 계속 틀리길래 구글링을 좀 해보니까, 결과값을 1000만으로 제한하는 것을 확인했다.

(100만도 된다)

그러니까 맞았는데,, 대체 왜일까?

진짜 모르겠다.

모른다고 코딩생활 끝나는건 아니니까 찾아보자.

for (int i = 1; i <= N; i++) {
		c = calfirst(c * i);
		a = calfirst(a * i);
		c= c % 10000000;
		a = a % 100000;

		t_c = c % 10;
		t_a = a % 10;
		if (t_a != t_c) {
			cout << "different : " << i;
		}
	}
    

단순하게 위와 같은 방법으로 찾아봤는데,
9375 , 15625 , 15626 , 15627이 다르다고한다.
N = 10만을 주면 다른 빈도가 더 늘어나는데 , 10만개 중에 15개만 다르다.

문제는 , 숫자가 곱해져서 0이 많이 만들어지는 경우 에 존재했다.

5자리 수 두개를 곱해서 0이 만들어질 수 있는 최대값은 10000x10000 -> 100000000 0이 8개까지 붙을수있다.

그럼 23000000 의 경우를 생각해보자. 나의 방식대로 10만으로 모듈러 연산을 하게 되면 결과값은 0이 된다.
하지만 1000만으로 하면 300만이 여전히 남는다.

반례는 이처럼 10만 모듈러 연산과 1000만 모듈러 연산의 차이가 생기는 부분에서 발생했으며 , 해결 방법은 처음부터 모듈러 연산을 1000만에서 해주는 것이다.