[C/C++] 백준 2553번 -마지막 팩토리얼 수

 

 

<코드>

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

long long n, ans;

int main()
{
	cin >> n;
	ans = 1;

	for (int i = 1; i <= n; i++)
	{
		ans *= i;
		ans %= 10000000; // 1천만
		while (ans % 10 == 0)
			ans /= 10;
	}
	cout << ans % 10 << '\n';

	
}

 

풀이 방법

팩토리얼의 경우 20!만 되도 수가 급격하게 커지기때문에 답을 구할 변수 ans의 크기를 10,000,000으로 제한해서 오버플로우가 발생하지않게 하였고 while문으로 오른쪽의 0들을 제거해주어 답을 출력하였다. 

 

처음에는 dp로

dp[i] = (dp[i-1]*i)%10 

로 하여 끝자리수들만 기억해서 곱한뒤 그 수의 1의 자리수를 저장하는 식의 논리를 사용하였지만,,,,

 

https://www.acmicpc.net/board/view/372

 

10으로 나눈 나머지수로는 앞에 어떠한 수가 있는지에 대한 모든 정보를 나타낼 수 없기때문에 그러한 논리는 답을 구할 수 없다.

 

 

 

 

www.acmicpc.net/problem/2553

2553번: 마지막 팩토리얼 수