BOJ 1676 - 팩토리얼 0의 개수

21 Mar 2017 on Algorithm

출처 BOJ

팩토리얼 0의 개수

문제

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

입력

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

출력

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

예제

풀이

뒤에서 처음 0이 아닌 숫자까지 0의 개수 = N!내에 (2x5)쌍의 개수
N!을 구성하는 2의 개수와 5의 개수를 구한 후 둘중 작은 값이 (2x5)쌍의 개수가 됨

코드

code

#include<cstdio>
#include<iostream>

using namespace std;

int N, cnt10;
int cnt2=0, cnt5=0;

int main(){
	scanf("%d",&N);

	for(int n=2; n<=N; n*=2)
		cnt2 += N/n;
	for(int n=5; n<=N; n*=5)
		cnt5 += N/n;
	cnt10 = min(cnt2,cnt5);

	printf("%d\n",cnt10);
}

복잡도

$O(N)$
2부터 N까지 검사 & 5부터 N까지 검사하므로