boj)1676 - 팩토리얼 0의 개수
2020. 9. 15. 21:13ㆍPS/boj
package soup.algorithms.boj;
import java.util.Scanner;
public class boj_1676 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int ans = 0;
for (int i = 5; i <= n; i*=5) {
ans += n/i;
}
System.out.println(ans);
}
}
- N 의 범위가 500까지인데 500! 구하는건 오래걸리고 수가 너무 크다 -> 다른 방법 생각
- 0이 뒤에 몇개가 오는가 ? -> 0이 될려면 소수 2 * 5가 되어야하고 결국 2 * 5가 몇 번 등장하는가 ?를 묻는것
- 어떤 수를 소인수분해 했을경우 2보다는 무조건 5가 적을수 밖에 없고 그렇다면 5의 등장 횟수를 찾아야한다.
- 1 ~ N의 수를 소인수 분해햇을경우 5의 등장횟수는 5를 나눈 몫과 같다.
- 그런데 25의 경우에는 5가 2번 등장, 125의 경우에는 5가 3번 등장 -> for문에서 증가값에 i *= 5를 줘서 추가로 카운팅해준다.
'PS > boj' 카테고리의 다른 글
boj)17087 - 숨바꼭질 6 (0) | 2020.09.15 |
---|---|
boj)9613 - GCD 합 (0) | 2020.09.15 |
boj)6588 - 골드바흐의 추측 (0) | 2020.09.15 |
boj)1929 - 소수 구하기 (0) | 2020.09.15 |
boj)17299 - 오등큰수 (0) | 2020.09.15 |