✨ 알고리즘 분류 : 수학, 정수론
https://www.acmicpc.net/problem/2004
2004번: 조합 0의 개수
첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다.
www.acmicpc.net
🪡 문제에서 요구하는 조건 정리
- nCm 에서 끝자리 0의 개수를 출력
- 최대값은 2,000,000,000
🧶 풀이과정
이것같은 경우는 전의 팩토리얼과 비슷하다
2024.04.08 - [Algorithm] - [053] 1676. 팩토리얼 0의 개수
[053] 1676. 팩토리얼 0의 개수
✨ 알고리즘 분류 : 수학 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🪡
jee-jeee.tistory.com
팩토리얼 때에는 5와 2 중 5만 선택했지만, 이번에는 2도 함께 센다는 것이 조금 다른 정도...?
조금 더 정리하자면
0이 제일 뒤에 온다는 것은 곧 10의 단위라는 것이다. 10은 곧 2x5 와 같기 때문에, 결국 2와 5의 수 중에 적은 쪽을 구하게 되면 그것이 10의 배수라는 것.
조금 더 가서, 조합에서 5의 개수를 세기 위해서는
(n에서의 5의 개수) - (n-m 에서의 5의 개수) - (m 에서의 5의 개수) 로 가져올 수 있다.
이제 각각 5의 수와 2의 수를 구하고 그것 중 적은 쪽을 출력하면 된다.
🏹 제출코드
package data_structure_part_01;
import java.io.*;
import java.util.StringTokenizer;
public class Q2004 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long n = Long.parseLong(st.nextToken());
long m = Long.parseLong(st.nextToken());
long countFive = fiveCount(n) - fiveCount(n - m) - fiveCount(m);
long countTwo = twoCount(n) - twoCount(n - m) - twoCount(m);
System.out.println(Math.min(countFive, countTwo));
br.close();
}
public static long fiveCount(long num){
long count = 0;
for(long i = 5; i <= num; i *= 5){
count += num / i;
}
return count;
}
public static long twoCount(long num){
long count = 0;
for(long i = 2; i <= num ; i *= 2){
count += num / i;
}
return count;
}
}
'Algorithm' 카테고리의 다른 글
[056] 11726. 2xn 타일링 (0) | 2024.04.11 |
---|---|
[055] 1463. 1로 만들기 (0) | 2024.04.09 |
[053] 1676. 팩토리얼 0의 개수 (0) | 2024.04.08 |
[052] 10872. 팩토리얼 (0) | 2024.04.08 |
[051] 6588. 골드바흐의 추측 (0) | 2024.04.05 |