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

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

1676번: 팩토리얼 0의 개수

 

이전에 풀었던 팩토리얼 만드는 코드에서 앞에서 한글자씩 스택에 넣을지 아니면 뒤에서부터 0의 유무를 검사할지 고민

 

시간 제한이 2초 

 

생각해보니  int 형의 자료형은 최대로 표현 가능한 양수의 최대값이 2,147,483,647인데 20!만 되도 24,329,020,000이므로 

N의 범위가 50까지인 이 문제에서는 다른 해결방법이 필요해 보였다.

 

처음으로 생각한 방법은 10을 만드는 방법이다. 2와 5를 곱하거나 10을 곱하는 방법이 있으므로 5!부터 1개 10!부터 2개 15!부터 3개 20!부터는 4개일것이라 생각해 이를 팩토리얼의 결과값을 계산하지 않고 5로 나누었을때 몫의 개수만 출력하였다.

 

#include <iostream>
using namespace std;

int main() {
int N, ans = 1;
cin >> N;

ans = N / 5;

cout << ans;

return 0;
}

 

틀렸기 때문에 뭐가 문제인지 고민하다가 100을 곱하게 되면 똑같은 5의 배수이지만 0이 2개 생기는 것을 깨달았고 접근 방법 자체를 소인수 분해를 통해 10의 갯수를 세어주어야겠다고 생각했는데 2는 5보다 훨씬 많이 나오지만 5가 곱해지지 않으면 0을 만들지 못하므로 5의 몇승인지만 알면 된다고 생각했다.

 

25는 5의 제곱이므로 5가 두개 들어간다. 125도 마찬가지로 5의 세제곱이므로 5가 세개들어간다. 따라서 5로 나누었을때의 몫의 갯수 뿐만아니라 25와 125로 나누었을때의 몫도 같이 구해서 결과값에 합쳐주었다.

 

 

#include <iostream>
using namespace std;

int main() {
int N, ans = 1;
cin >> N;

ans = N / 5;

ans += N / 25;

ans += N / 125;


cout << ans;

return 0;
}

 

-> 다시 올리기