[BOJ][C++] 백준 1676번 팩토리얼 0의 개수
Updated:
1676번 팩토리얼 0의 개수
1. 문제 정보
백준 온라인 저지 [1676번 팩토리얼 0의 개수] 문제의 링크입니다.
문제
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)
출력
첫째 줄에 구한 0의 개수를 출력한다.
예제 입력1
10
예제 출력1
2
시간 / 메모리 제한
2초 / 128MB
2. 생각
-
먼저 n!을 구한 뒤에 그 값을 10으로 나누며 나누어 떨어진다면 0을 카운트 하고 나누어 떨어지지 않는다면 카운트 하지 않고 반복문을 탈출하면 됩니다.
-
그런데 입력을 보니 n의 최대값이 500입니다. 따라서 500!을 표현할 수 없기 때문에 다른 방법을 생각합니다.
-
숫자의 끝 자리에 0이 오려면 10이 곱해져야합니다. n!의 모든 숫자의 곱에서 2와 5의 쌍을 찾는 방법으로 접근해야합니다.
A * 10^x
- 그런데 숫자들의 곱에서 짝수에는 모두 2가 있으므로 5보다 2의 개수가 항상 많습니다. 따라서 5의 개수를 세는 것이 더 빠릅니다. 5는 5의 배수에 있으므로 5로 나눈 몫(개수)을 세고, 5의 제곱(25), 5의 세 제곱(125)의 경우에는 5가 각각 2개, 3개 있으므로 이것도 나누어 셉니다.
3. 소스코드 (C++)
