[algorithm] 백준 - 조합 0의 개수

우선 곱셈으로 0을 어떻게 만들 수 있을까?

2와 5가 곱해졌을 때 10으로 0의 개수가 1이다.

4와 25가 곱해졌을 때 100으로 0의 개수가 2이다.

즉 2와 5는 0을 만드는 구성원이라는 것을 알 수 있다.

 

그렇다면 2가 1개 5가 1개일 때 0 1개를 만들 수 있다.

2가 2개 3개더라도 5는 1개이면

0은 언제나 1개이다.

 

즉 2와 5의 개수 중 가장 작은 수가 0의 개수이다.

 

조합은

라는 식을 갖는다.

 

그렇다면 n!에서의 2의 개수 - k! 에서의 2의 개수 - (n-k)! 에서의 2의 개수와

n!에서의 5의 개수 - k! 에서의 5의 개수 - (n-k)! 에서의 5의 개수 중 가장 작은 수는 0의 개수라는 것을 알 수 있다.

 

cout << min(countFive(n) - countFive(m) - countFive(n - m)
    , countTwo(n) - countTwo(m) - countTwo(n - m));

그럼 0의 개수를 구하는 법은 알았는데,

2의 개수와 5의 개수는 어떻게 구할까?

 

단순하게 구구단을 생각해보자.

 

5 * 1 = 5

5 * 2 = 10

5 * 3 = 15

5 * 4 = 20

5 * 5 = 25

...

25 * 1 = 25

25 * 2 = 50

...

125 * 1 = 125

125 * 2 = 250

 

 

이렇듯이 숫자 / 5를 하게 되면 숫자 ! 에서 5의 개수를 알 수 있다.

그리고 위에서 언급했듯이,

2와 5가 곱해졌을 때 10으로 0의 개수는 1이다.

4와 25가 곱해졌을 때 100으로 0의 개수는 2이다.

8과 125가 곱해졌을 때 1000으로 0의 개수는 3이다.

...

 

즉 2^n * 5 ^n 을 연산했을 때 0의 개수는 n개라는 것을 알 수 있다.

그렇다면 반복문을 돌릴 때 3 번째 조건으로 i *= 2나 i *= 5를 해줘야한다는 것을 알 수 있다.

 

따라서

long long countFive(long long num){
    int fiveCount = 0;
    for(long long i = 5; i <= num; i*=5){
        fiveCount += num / i;
    }
    return fiveCount;
}

long long countTwo(long long num){
    int twoCount = 0;
    for(long long i = 2; i <= num; i*=2){
        twoCount += num / i;
    }
    return twoCount;
}

 

이런 식으로 2의 개수와 5의 개수를 구할 수 있다.

 

코드는

//조합 0의 개수
#include <iostream>
using namespace std;

long long countFive(long long num){
    int fiveCount = 0;
    for(long long i = 5; i <= num; i*=5){
        fiveCount += num / i;
    }
    return fiveCount;
}
long long countTwo(long long num){
    int twoCount = 0;
    for(long long i = 2; i <= num; i*=2){
        twoCount += num / i;
    }
    return twoCount;
}
int main(void){
    long long n,m;
    cin >> n >> m;
    cout << min(countFive(n) - countFive(m) - countFive(n - m)
    , countTwo(n) - countTwo(m) - countTwo(n - m));
}