백준 2004번 조합 0의 개수 자바 Java (☆공부 248일차)

2004 조합 0의 개수

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

2004번: 조합 0의 개수

 

 

 

---

백준 2004번 문제 조합 0의 개수

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	47375	13329	11002	28.715%

문제

$n \choose m$의 끝자리 $0$의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다.

출력

첫째 줄에 $n \choose m$의 끝자리 $0$의 개수를 출력한다.

제한

 

예제 입력 1

25 12

예제 출력 1

2

힌트

 

 

 

 

---

과정 생각해보기

---

 

 

https://gimbalja.tistory.com/177

공부 98일차: 백준 2004번 조합 0의 개수 자바 java

 

4달 전에 풀었던 문제

 

이전 풀이와 같다

0의 개수를 구한다 = 10이 되는 걸 생각한다 = 2와 5 중 수가 적은 개수만큼 생긴다라는 게 핵심

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        // ★ n-m
        int twoCnt = getCnt(n, 2) - getCnt(n-m, 2) - getCnt(m, 2);
        int fiveCnt = getCnt(n, 5) - getCnt(n-m, 5) - getCnt(m, 5);
        
        System.out.println(Math.min(twoCnt, fiveCnt));
        br.close();
    }
    
    // ★
    static int getCnt(int num, int divisor) {
        int count = 0;
        while(num >= divisor) {
            count += num/divisor;
            num /= divisor;
        }
        return count;
    }
}
 

 

 

 

---

이전엔 BufferedWriter를 썼지만 출력이 간단한 문제라서 차이는 크지 않다

오히려 메모리를 더 적게 쓴다