[BOJ][C++] 백준 2004번 조합 0의 개수
Updated:
2004번 조합 0의 개수
1. 문제 정보
백준 온라인 저지 [2004번 조합 0의 개수] 문제의 링크입니다.
문제
nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다.
출력
첫째 줄에 0의 개수를 출력한다.
예제 입력1
25 12
예제 출력1
2
시간 / 메모리 제한
2초 / 128MB
2. 생각
- 문제 1676번 팩토리얼 0의 개수 문제를 활용하여 풀 수 있습니다.
- 문제 1676과는 다른 점은 n!이 아닌 조합이라는 점입니다.
조합은 다음과 같이 구합니다.
nCm = n! / (n-m)! * m!
- n!, (n-m)!, m!의 2와 5의 조합의 개수를 구합니다. 그리고 n!의 개수에서 (n-m)!과 m!의 개수를 빼야합니다. 조합을 구할 때는 나눗셈을 포함하므로 문제 1676처럼 5의 개수만 세면 안됩니다.
예) 25 12
25!
2의 개수 5의 개수 22 6 (25-12)! = 13!
2의 개수 5의 개수 10 2 12!
2의 개수 5의 개수 10 2
2의 개수 = 22 - 10 - 10 = 2, 5의 개수 = 6 - 2 - 2 = 2
이 예에서는 값이 같지만 두 값중 작은 값을 선택하여 출력합니다.
3. 소스코드 (C++)
