[Baekjoon/백준] 1676번: 팩토리얼 0의 개수(C/C++)

단계별로 풀어보기 17단계(정수론 및 조합론) 11번 문제

https://www.acmicpc.net/step/18

정수론 및 조합론 단계

---

백준 1676번: 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

---

문제 설명

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

---

입력과 출력

입력: 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력: 첫째 줄에 구한 0의 개수를 출력한다.

---

접근 방법

이번 문제는 N을 입력받아 N!에서 나온 값의 끝자리 0의 개수를 출력하는 문제다. 예제 1번의 경우 결과값이 3628800이 나온다. 그래서 출력값이 2가 나오게 된다.

끝자리 0의 개수는 10의 약수인 2와 5의 개수 중 작은 것으로 알 수 있다. 이번 문제는 그냥 팩토리얼을 계산하므로 당연히 5가 더 적을 것이다. 따라서 5의 개수만 구하면 된다. 앞의 예제인 10의 경우 5, 10이 5의 배수가 된다. 그래서 2개가 출력된다. 하지만, 25의 경우 5의 배수가 5, 10, 15, 20, 25로 5개가 나올 것 같지만 결괏값이 15,511,210,043,330,985,984,000,000로 0이 6개다. 이경우에는 25가 5*5이므로 그렇다. 그래서 5를 나누는 것까지 고려해야한다. 즉, 팩토리얼 연산 중 5로 나눠서 0인 것과 그것을 또 5로 나눠서 나오는 5의 배수 개수를 출력하면 문제를 해결할 수 있다.

---

코드

#include <iostream>
using namespace std;

int main(int argc, char * argv[]) {
	int N, count, temp, result = 0;
	cin >> N;
	
	for (int i = 1; i <= N; i++) {
		count = 0;
		temp = i;
		while (1) {
			if (temp % 5 == 0) {
				count++;
				temp /= 5;
			}
			else
				break;
		}
		result += count;
	}

	cout << result << endl;

	return 0;
}

---

결과

백준 제출 결과