백준 1676번 팩토리얼 0의 개수 자바 Java (☆공부 247일차)

1676 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

 

 

 

---

백준 1676번 문제 팩토리얼 0의 개수

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	59071	28449	23568	47.902%

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

제한

 

예제 입력 1

10

예제 출력 1

2

예제 입력 2

3

예제 출력 2

0

힌트

 

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/176

공부 97일차: 백준 1676번 팩토리얼 0의 개수 자바 java

 

4달 전에 풀었던 문제

 

기존 설명과 풀이가 괜찮아서 그대로 올린다

 

주어진 n의 범위가 0부터 500인데, 500! 이라면 엄청 큰 수라는 걸 알 수 있다

10!만 하더라도 3628800이 나오니 말이다

 

그래서 500!을 직접 구하기보다는, 0이 붙을 때마다 카운트를 +1하는 것이 맞는 방향이라고 할 수 있겠다

0이 붙을 수 있는 경우를 생각해보면,

 

1) 10, 100, 300 등 10의 배수로 나눴을 때 나머지가 없는(딱 나누어 떨어지는) 수들

2) 5*2, 15*4 등 2와 5의 배수를 곱했을 때

 

다른 것처럼 나눠놨지만 결국 같은 말을 하고 있다

두 가지 경우의 공통점은 모두 10, 즉 2*5가 들어간다는 것이다

 

결국 0의 개수를 구한다는 것은 2와 5가 몇 번 같이 나오는지를 세는 것과 같다

 

 

모든 수를 소인수분해해보면 2는 항상 5보다 많이 등장하므로, 5의 개수만 세면 된다

방법은 두 가지로 나눌 수 있다

 

1) 반복문으로 5의 개수를 세는 경우

2) 5, 25(5*5), 125(5*5*5)의 배수가 나올 때마다 개수 세기(5*5*5*5=625 > 500이라 제외)

 

 

---

정답 인정 코드

---

 

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

 

 

 

---

같은 풀이라서 똑같음

br.close()를 추가해서 메모리만 아주 조금 줄었다