Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

17. 정수론 및 조합론

정수론과 조합론을 배워 봅시다.

Java / Python

11. 팩토리얼 0의 개수

1676번

소인수분해의 성질을 활용하여 N!의 끝에 0이 얼마나 많이 오는지 구하는 문제

이번 문제는 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제입니다.
문제를 살펴보면, 뒷자리가 0이 n개 있다는 의미는 2와 5가 n개씩 짝지어 존재한다는 것이라고 볼 수 있습니다.
기본적으로 5의 개수에 따라 값이 변화한다고 보고, 5의 n제곱에 따라 카운트를 1씩 증가시킵니다. 즉, 단순히 5로 나눌 것이 아니라 반복문을 통해 5로 나누면서 누적합을 해주는 방식입니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int num = Integer.parseInt(br.readLine());
		int cnt = 0;
 
		while (num >= 5) {
			cnt += num / 5;
			num /= 5;
		}
		System.out.println(cnt);
	}
 
}

• Python

import sys

num = int(sys.stdin.readline())
cnt = 0
 
while (num >= 5):
	cnt += num // 5
	num //= 5;

print(cnt)