빠똥빠똥
2004번 조합 0의 개수 - ☆ 본문
#문제링크 : https://www.acmicpc.net/problem/2004
<전략>
1. n!의 0의 갯수는 1~n까지 5가 몇번나오느냐와 같다. 0은 2 x 5 = 10 으로부터 나오기 때문인데, 2는 5에 비해 훨씬 많이 나오게 된다. 따라서 소인수분해 했을때, 5가 몇번 나오는지만 세어주면 뒤에 붙는 0에 갯수를 알 수 있다.
2. 반면, 조합은 2와 5중 어떤것이 더 많이 도출되는지 알 수 없다. 따라서 2와 5중에서 더 적게 나오는 수의 갯수가 0의 갯수가 된다.
'백준' 카테고리의 다른 글
11729번 하노이 탑 이동 순서(재귀, pow, 입출력) - ☆ (0) | 2020.07.13 |
---|---|
2447번 별 찍기10(재귀) - ☆ (0) | 2020.07.13 |
11721번 열 개씩 끊어 출력하기(getchar(), EOF) - ☆ (0) | 2020.07.12 |
11718번 그대로 출력하기(getline) - ☆ (0) | 2020.07.12 |
1002번 터렛(원) - ☆ (0) | 2020.07.12 |