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

1676 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

 

 

 

---

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

---

문제

---

 

 

 

---

과정 생각해보기

---

 

주어진 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이라 제외)

 

 

 

---

정답 인정 코드

---

 

1) 5, 25, 125 활용

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;
        
        count += n/5;    // 5^1
        count += n/25;    // 5^2
        count += n/125;    // 5^3
        
        // n이 5보다 작을 경우 0, 즉 count의 초기값을 그대로 가져가므로 따로 계산할 필요 없다
 
        System.out.println(count);
    }
    
 
}

 

for문 안에 while문을 반복하고 count를 1씩 늘려보는 방법은 시간 초과가 떠서 사용한 방법

 

 

 

2)

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;
        }
        // n이 5보다 작을 경우 0, 즉 count의 초기값을 그대로 가져가므로 따로 계산할 필요 없다
 
        System.out.println(count);
    }
    
 
}

 

https://st-lab.tistory.com/165

이 블로그에 더 간단한 방법이 있어서 옮겨봤다

 

결국 1번 풀이와 같은 방식이긴 하다

 

 

 

 

---