2004. 조합 0의 개수

문제링크 : https://www.acmicpc.net/problem/2004

< 입력 >

정수 n,m (0<=m<=n<=2,000,000,000)

< 출력 >

nCm의 일의 자리부터 연속된 0의 개수

< 풀이 >

우선 0의 개수라는 말을 보자마자 2 * 5가 몇 개 들어가는지 묻는 문제라는 것을 떠올려야 한다.

2와 5의 개수를 찾아주기 위해 nCm을 구해보자.

물론 n과 m의 범위가 2*10^9이기 때문에 n을 m개, m! 확인하면 당연히 초과가 난다.

그래서 nCm의 공식을 알아야 한다.

nCm의 공식은 n! / (m! * (n-m)!) 이다.

n!에 2와 5개 몇개 들어갈까?

n보다 작거나 같은 자연수 중에 2의 배수의 개수를 통해 구할 수 있다.

n을 2로 나눈다. 이는 n보다 작거나 같은 2의 배수의 개수이다.

다음으로 n/2를 다시 2로 나눈다. 이는 n보다 작거나 같은 4(2^2)의 배수의 개수이다.

즉, 2가 2번 곱해진 경우이므로 (n/2)/2만큼의 개수를 추가해줘야 한다.

이렇게 n이 2보다 크거나 같을 동안 반복하게 되면 n!에 포함된 2의 개수를 알 수 있다.

5도 마찬가지로 진행해서 2의 개수와 5의 개수 중 최소값을 구한다면 0의 개수를 구할 수 있다.

---

- 소스 코드 -

/*
 * 공간복잡도 : O(1)
 * 시간복잡도 : O(logn) (밑 수는 2)
 * 
 * nCm의 결과는 n! / m! * (n-m)!입니다.
 * 처음에는 당연히 5의 배수가 더 적을 것이라고 생각하고
 * 5의 배수만 계산하다 맞왜틀 했습니다..
 * 26C2와 같은 예외가 있더라구요 !!
 * 그래서 2의 배수도 같은 방식으로 구해서
 * 둘 중에 최소값을 결과로 출력했습니다.
*/
 
#include<iostream>
 
using namespace std;
 
typedef long long ll;
 
int main(void){
    int a,b;
    cin>>a>>b;
    int c=a-b;
    int tempA,tempB,tempC;
    tempA=a; tempB=b; tempC=c;
    ll aCount1=0; ll bCount1=0; ll cCount1=0; // 2의 배수
    ll aCount2=0; ll bCount2=0; ll cCount2=0; // 5의 배수
 
    while(tempA>=2){
        tempA/=2;
        aCount1+=tempA;
    }
    while(tempB>=2){
        tempB/=2;
        bCount1+=tempB;
    }
    while(tempC>=2){
        tempC/=2;
        cCount1+=tempC;
    }
    while(a>=5){
        a/=5;
        aCount2+=a;
    }
    while(b>=5){
        b/=5;
        bCount2+=b;
    }
    while(c>=5){
        c/=5;
        cCount2+=c;
    }
    ll result1=aCount1-bCount1-cCount1;
    ll result2=aCount2-bCount2-cCount2;
    result1>result2?cout<<result2<<endl:cout<<result1<<endl;
}

---