[053] 1676. 팩토리얼 0의 개수

✨ 알고리즘 분류 : 수학

 

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

1676번: 팩토리얼 0의 개수

 

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- N! 에서 맨 뒤의 연속되는 0의 개수 구하기

 

🧶 풀이과정 

 

내가 팩토리얼을 잘 몰라서, 찾아보면서 알게 되었는데

뒤에 있는 0의 갯수는 결국 5x2의 갯수였다. 그러니까, 10의 배수가 들어갈 때 제일 뒤에 0이 붙는 구조라고 보면 된다.

2는 5보다 많이 등장하기 때문에 (5가 들어가면 무조건 앞에는 2가 있기 때문에 5를 센다는 건 결국 2*5를 세는 것과 같다) 들어가는 5의 배수를 찾으면 된다.

 

예를 들어서 10이라면

1 2 3 4 5 6 7 8 9 10을 곱하게 되는데, 여기에서 5의 배수인 5, 10(5x2)이니까 뒤에 있는 0의 개수는 2가 되는 구조이다.

 

이걸 코드에 조금 더 쉽게 녹이면

10이라면 i를 5로 하여 n까지 오는 수 중에 i가 몇개나 오는지 센다 (n/i)

이후에 5의 거듭제곱을 하여, 다음 수에서 n에 i가 몇개가 나오는지 센다.

! 왜 거듭제곱으로 세는가? 를 보면  25의 경우 5x5이므로 5가 두개! 그러므로 각각 카운트해야한다. 

- 최소공배수에서 5의 갯수를 센다고 보면 된다

 

 

🏹 제출코드

 

import java.io.*;

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int cnt = 0;
        for(int i = 5; i <= n; i *= 5){
            
            cnt += n / i;
        }

        bw.write(cnt + "");
        

        bw.flush();
        bw.close();
        br.close();
    }
}